\documentclass[a4paper]{report} 
\usepackage[dutch]{babel}
\usepackage{graphicx}
\usepackage{subfig}
\usepackage{ctable}
\usepackage{color}
\usepackage{listings}
\lstset{%
language=C++,%
basicstyle=\footnotesize,%
numbers=left,%
numberstyle=\footnotesize,%
stepnumber=1,%
numbersep=5pt,%
backgroundcolor=\color{white},%
showspaces=false,%
showstringspaces=false,%
showtabs=false,%
frame=single,%
tabsize=2,%
captionpos=b,%
breaklines=true,%
breakatwhitespace=false,%
escapeinside={\%}{)}, %
mathescape={true} %
}
\author{Ruben van Haaster\\\\Promotor: Marc Gyssens\\\\Begeleider: Bart Moelans}
\title{Visualiseren van Graafalgoritmen}
\date{}

\newcommand{\class}[1]{\texttt{#1}}
\newcommand{\function}[1]{\texttt{\footnotesize#1}}

\begin{document}
% \maketitle
\input{./title.tex}
\newpage

\begin{center}
{\textbf {\large Woord Vooraf} }\\[.5cm]
\end{center}

\noindent Dit verslag maakt deel uit van mijn bachelorproef over het visualizeren van graafalgoritmen, voorgedragen tot het behalen van de graad van bachelor in de informatica aan de Universiteit Hasselt. In dit verslag bespreek ik grafen, graafproblemen, algoritmen die deze problemen op zullen lossen, en visualizaties die zullen helpen deze oplossingen beter te kunnen begrijpen.

Mijn dank aan promotor Prof. Dr. Marc Gyssens en begeleider Bart Moelans, voor hun geduld, aanwijzingen en inspiratie, zonder welke ik dit project niet tot in de huidige staat gekregen zou hebben.


\newpage
\tableofcontents
\newpage

\chapter{Inleiding}
\section{Inleiding}
Veel situaties zijn te representeren door grafen. Indien men informatie over een dergelijke situatie probeert te winnen, kan dit vaak vertaald worden in een graafprobleem. De oplossing van dit probleem, het algoritme dat gebruikt kan worden om informatie over deze situatie te winnen, is in de regel niet simpel te vatten. Hoe kan men er zeker van zijn wat een algoritme precies doet, of het wel daadwerkelijk de informatie helpt bemachtigen waar iemand naar op zoek is?

Dit thesisproject handelt rond deze problematiek. Er zal getracht worden het begrip van een algoritme gemakkelijker te begrijpen te maken, door de werking van dit algoritme visueel weer te geven. Dit eerste hoofdstuk zal handelen rond de context waarin gewerkt zal worden. Ook zal het enkele voorbeelden bevatten waar getoond wordt hoe een visualisering behulpzaam kan zijn om een algoritme beter te begrijpen.

Hoofdstuk~\ref{section:Gebruik} zal uitleggen hoe het framework voor visualisatie gebruikt kan worden. Hoofdstuk~\ref{section:Werking} zal handelen rond de preciese werking van dit framework. Tot slot zal hoofdstuk~\ref{section:Visualizaties} enkele visualizaties tonen door dit framework.

\section{Een graaf}
Een graaf is een verzameling van knopen en bogen, ookwel nodes en edges (of paden) genoemd. Deze paden zullen altijd een knoop met een andere, ofwel dezelfde knoop verbinden. Sommige grafen laten toe dat een pad enkel in \'e\'en richting `bewandeld' wordt, terwijl andere grafen toelaten deze in beide richtingen te doorlopen. Buiten dit is het ook mogelijk dat een graaf knopen bevat die helemee niet met een pad verbonden worden met de rest, of zelfs dat een graaf bestaat uit twee of meer deelgrafen die onderling niet verbonden zijn.

\begin{figure}[h!]
\centering
	\begin{tabular}{|c|c|c|}
	\hline
	\\
	\includegraphics[scale=.35]{images/graph1.png}&
	\includegraphics[scale=.3]{images/graph2.png}&
	\includegraphics[scale=.25]{images/graph3.png}
	\\
	\hline
	\end{tabular}
\caption{Verschillende grafen}
\label{Image:Graph}
\end{figure}

In figuur~\ref{Image:Graph} ziet men drie verschillende grafen die ieder op zich enigszins bijzonder zijn. Van links naar rechts is de eerste een zeer simpele, bidirectionele graaf. Dit betekent dat de paden in beide richtingen te bewandelen zijn. Alle knopen zijn hier ook onderling door paden verbonden. 

De tweede graaf is een voorbeeld van een directionele graaf; paden kunnen hier enkel in \'e\'en richting doorlopen worden. Hier valt meteen op dat we \'e\'en knoop hebben die totaal niet verbonden is met de rest van de andere knopen. Ook merken we dat het toegelaten is meerdere paden van de ene naar de andere knoop in een graaf te hebben. Tot slot merken we ook op dat de bogen hier een label dragen, die in dit geval bijvoorbeeld de kost van het bewandelen van een pad zouden kunnen beschrijven. 

Uiteindelijk bekijken we ook de derde graaf. Deze is speciaal omdat het in feite een boom is. Vanaf de bovenste knoop (gelabeld met een 1), kan er enkel verder naar beneden gelopen worden. In dit geval is ook getoond dat ook de knopen zelf een label mogen dragen, zelf al hebben de bogen dat in dit geval niet.

Een graaf is een datastructuur die gebruikt kan worden om zeer veel verschillende situaties mee te modelleren. In het meest voordehandliggende voorbeeld stelt iedere knoop een locatie voor, en iedere boog en weg tussen deze locaties, waar de labels op de bogen gebruikt worden om de tijd uit te drukken die het kost om dat traject te nemen, van de ene naar de andere locatie. Er zijn echter veel meer situaties die door een graaf gemodelleerd kunnen worden, zoals bijvoorbeeld een LAN netwerk.

Om alles nogmaals zeer kort samen te vatten kunnen we op deze wijze een graaf defini\"eren:
\begin{itemize}
\item Graaf:
	\begin{itemize}
		\item Is ofwel gericht ofwel ongericht.
		\item Bevat knopen:
		\begin{itemize}
			\item Een knoop kan een label dragen.
			\item Een knoop is uniek.
		\end{itemize}
		\item Bevat bogen:
		\begin{itemize}
			\item Een boog verbindt precies twee knopen.
			\item Een boog kan een label dragen.
			\item Alle bogen in een graaf kunnen ofwel in \'e\'en ofwel in beide richtingen doorlopen worden, afhankelijk van of de graaf gericht is.
			\item Een boog kan een knoop met zichzelf verbinden.
			\item Bogen zijn niet uniek. Er kunnen twee of meer bogen tussen dezelfde twee knopen zijn, eventueel zelfs met hetzelfde label.
		\end{itemize}
	\end{itemize}
\end{itemize}

\section{Een probleem met een graaf}
In de vorige sectie is besproken hoe een graaf een bepaalde situatie voor kan stellen. Uiteraard willen we deze datastructuur dan gebruiken om meer informatie over de situatie die zij voorstelt te winnen dan we op het moment beschikbaar zijn. Het winnen van informatie, welk zo eenvoudig kan zijn als het beantwoorden van een ja/nee-vraag, ligt aan het hart van een graafprobleem.

Voor een groot deel van de vragen over informatie over de graaf is ook een antwoord beschikbaar. Dit antwoord wordt verkregen door een algoritme op deze graaf uit te voeren. Een algoritme kan bekeken worden als een soort stappenplan om de gewenste informatie te bemachtigen.

Een voorbeeld van een zeer bekend probleem is het handelsreizigersprobleem. In dit geval wordt de graaf gebruikt om inderdaad locaties voor te stellen. Het probleem met deze graaf is dan: ``Is het mogelijk iedere locatie precies eenmaal te bezoeken, en aan het einde van de rit alle locaties bezocht te hebben?''.

Om een voorbeeld van een algoritme te geven, is het het makkelijkst het een oplossing voor het PATH\cite[p.~263]{complexiteit} probleem te illustreren. Gegeven een graaf, dan is het probleem als volgt. ``Bestaat er een pad tussen de start-knoop en een willekeurige eindknoop?''. Als we de tweede graaf van figuur~\ref{Image:Graph} bekijken, weten wij bijvoorbeeld meteen dat als knoop 1 een start- of eindknoop is, er inderdaat geen pad mogelijk zal zijn.

De pseudo-code in listing~\ref{Alg:Path} geeft een voorbeeld van een algoritme, een voorbeeld van hoe die PATH probleem opgelost kan worden.

\begin{lstlisting}[language={}, caption={PATH algoritme}, label={Alg:Path}]
Zij $l$ een lijst van knopen.
Neem knoop $0$ de startknoop.
Voeg $0$ toe aan $l$.
Voor iedere knoop $k$ in $l$ doe:
	Voor iedere boog $b$ in de graaf doe:
		Als $b$ begint in $k$:
			Zij $x$ de knoop waarin $b$ aankomt.
			Als $x \not\in l$: Voeg $x$ toe in $l$.
\end{lstlisting}

In listing~\ref{Alg:Path} zien we dan inderdaad een stappenplan dat uitgevoerd kan worden met een bepaalde graaf als input, dat uiteindelijk in haar lijst $l$ alle knopen zal bevatten die vanuit de startknoop bereikbaar zijn. In het bijzonder, als we willen weten of knoop $x$ bereikbaar is, kunnen we dat aan het einde van het algoritme testen, door te kijken of deze knoop zich in de lijst $l$ bevat.

\section{Visualiseren van algoritmen}
\subsection{Path probleem}
Dit thesisproject handelt rond het visualiseren van algoritmen die op grafen werken. Een eerste vraag die men hierbij kan stellen is, ``Waar is dit voor nodig?''. Het algoritme in listing~\ref{Alg:Path} vormt op zich al een aardig argument. Men kan dit algoritme bekijken, maar in deze vorm is het zeer moeilijk in te zien hoe het precies werkt en wat het doet. Het nut van visualiseren is, bijvoorbeeld, om een algoritme zoals het vorige op een begrijpbare manier te kunnen tonen.

\ctable[pos=h!t, botcap, figure, caption={Startgraaf}, label={AlgPath:Begin}]{c}{}{
\includegraphics[scale=.35]{images/AlgPath/graph_screen_1.png}
}

In figuur~\ref{AlgPath:Begin} ziet men de graaf waarom dit algoritme uitgevoerd zal worden. In figuur~\ref{AlgPath:Exec} kan men een visualisatie van dit algoritme bekijken.

\ctable[pos=h!t, botcap, figure, caption={Visualisatie PATH}, label={AlgPath:Exec}]{ccc}{}{
\includegraphics[scale=.35]{images/AlgPath/graph_screen_2.png}&
\includegraphics[scale=.35]{images/AlgPath/graph_screen_3.png}&
\includegraphics[scale=.35]{images/AlgPath/graph_screen_4.png}
\\
(1) & (2) & (3)
\\
\includegraphics[scale=.35]{images/AlgPath/graph_screen_5.png}&
\includegraphics[scale=.35]{images/AlgPath/graph_screen_6.png}&
\includegraphics[scale=.35]{images/AlgPath/graph_screen_7.png}
\\
(4) & (5) & (6)
\\
\includegraphics[scale=.35]{images/AlgPath/graph_screen_8.png}&
\includegraphics[scale=.35]{images/AlgPath/graph_screen_9.png}&
\includegraphics[scale=.35]{images/AlgPath/graph_screen_10.png}
\\
(7) & (8) & (9)
\\
\includegraphics[scale=.35]{images/AlgPath/graph_screen_11.png}&
\includegraphics[scale=.35]{images/AlgPath/graph_screen_12.png}&
\\
(10) & (11) &
}

Nu kunnen we het verloop van het algoritme op de volgende manier uitleggen.
\begin{enumerate}
\item We markeren de beginknoop rood. Deze is uiteraard bereikbaar. We zijn er al!
\item We bekijken een willekeurige boog vanuit de beginknoop. Deze markeren we groen.
\item De eindknoop van laatst gemarkeerde boog kennen we nog niet. We markeren deze rood, het is dus bereikbaar.
\item We bekijken een volgende boog en markeren deze.
\item Ook haar eindknoop kennen we nog niet, dus markeren we deze.
\item We bekijken een volgende boog.
\item Haar eindknoop kennen we, dus wordt deze niet gemarkeerd. We bekijken een volgende boog.
\item Ook haar eindknoop kennen we. We gaan verder vanuit een nieuwe bereikbare (gemarkeerde) knoop. Vanuit deze (knoop 3), nemen we weer een willekeurige boog en markeren deze.
\item Haar eindknoop (knoop 4) kennen we weer, dus beschouwen we weer een volgende boog.
\item Knoop 5 is nog niet gemarkeerd. Deze markeren we nu.
\item Tot slot is er nog \'e\'en boog over. Deze helpt ons geen nieuwe knopen kennen. Het algoritme is nu over, en we zien dat we vanuit de startknoop (knoop 2) de knopen 3, 4 en 5 kunnen bereiken. Knoop 1 is niet gemarkeerd, er is dus geen pad beschikbaar.
\end{enumerate}

\subsection{Minimale omspannende boom van een graaf}
Een ander voorbeeld van een algoritme dat op een graaf werkt is Kruskal's algoritme\cite[p.~231]{cursus}. Gegeven een gewogen graaf (dit wil zeggen, een graaf waar alle paden een bepaalde kost hebben), zal dit algoritme de minimale omspannende boom vinden. Dit zal een boom zijn die alle knopen van gegeven graaf bevat, maar ook de minste totale kost van alle paden zal hebben.

Kruskals algoritme kan beschreven worden zoals in listing~\ref{Alg:Kruskal}.

\begin{lstlisting}[language={}, label={Alg:Kruskal}, caption={Kruskals algoritme}]
Maak een verzameling van bomen $F$, zodat elke knoop van de graaf in %\'e\'en) aparte boom zit.
Maak een verzameling $S$ van alle bogen van de graaf.
Zolang $S$ niet leeg is, doe:
	Verwijder een boog met minimum gewicht uit $S$. Noem deze boog $B$.
	Als $B$ twee verschillende bomen verbindt: 
		Verwijder de twee bomen $b_1$ en $b_2$ uit $F$.
		Verdind $b_1$ en $b_2$ door $B$. Noem het resultaat $b'$.
		Voeg $b'$ toe aan $F$.
$F$ bevat nu slechts %\'e\'en) element, de minimum omspannende boom voor gegeven graaf.
\end{lstlisting}

Zoals bij het algoritme voor het PATH probleem, is het weer enigszins ongemakkelijk in te zien hoe dit algoritme in de praktijk werkt. Stel nu dat we dit uitvoeren op de graaf in figuur~\ref{AlgKruskal:Begin}, dan zal het algoritme precies zo te werk gaan als getoond in figuur~\ref{AlgKruskal:Exec}.

\ctable[pos=h!t, botcap, figure, caption={Startgraaf}, label={AlgKruskal:Begin}]{c}{}{
\includegraphics[scale=.35]{images/AlgKruskal/graph_screen_1.png}
}

\ctable[pos=h!t, botcap, figure, caption={Uitvoering Kruskals algoritme}, label={AlgKruskal:Exec}]{cccc}{}{
\includegraphics[scale=.35]{images/AlgKruskal/graph_screen_2.png}&
\includegraphics[scale=.35]{images/AlgKruskal/graph_screen_3.png}&
\includegraphics[scale=.35]{images/AlgKruskal/graph_screen_4.png}&
\includegraphics[scale=.35]{images/AlgKruskal/graph_screen_5.png}
\\
(1)&(2)&(3)&(4)
\\
\includegraphics[scale=.35]{images/AlgKruskal/graph_screen_6.png}&
\includegraphics[scale=.35]{images/AlgKruskal/graph_screen_7.png}&
\includegraphics[scale=.35]{images/AlgKruskal/graph_screen_8.png}&
\\
(5)&(6)&(7)&
}

De werking van het algoritme van Kruskal zoals getoond in figuur~\ref{AlgKruskal:Exec}, uitgevoerd op de graaf getoond in figuur~\ref{AlgKruskal:Begin}, kan dan toegelicht worden als volgt.
\begin{enumerate}
\item Als boog met minimum gewicht kiezen we $A\rightarrow D$. Merk op dat dit een willekeurige keuze is, $C\rightarrow E$ heeft namelijk dezelfde kost. We verbinden deze `bomen' met elkaar en markeren ze.
\item Zoals eerder vermeld kiezen we nu $C\rightarrow E$. Weer markeren we deze.
\item De volgende laagste kost om twee verschillende bomen te verbinden is 6, we kiezen dus $D\rightarrow F$ en markeren deze.
\item Willekeurig voor kost 7 kiezen we $A\rightarrow B$.
\item Voor dezelfde kost kunnen we nu $B\rightarrow E$ markeren.
\item De volgende laagste kost zou 8 zijn, voor $E\rightarrow F$. Merk op dat beide knopen $E$ en $F$ al onderling vorbonden zijn, dus in dezelfde boom zitten. We kiezen nu $E\rightarrow G$ voor kost 9.
\item Alle knopen zitten nu in \'e\'en en dezelfde boom. Dit wordt het duidelijkst getoond door alle paden van de graaf die we niet gebruikt hebben, te verwijderen. In deze deelfiguur ziet men het resultaat.
\end{enumerate}

\subsection{Conclusie}
In de twee vorige secties zijn twee graafproblemen beschreven. Voor beide problemen is een algoritme gegeven dat dit op kan lossen. Deze algoritmen waren beschreven op een manier die volstaat om het algoritme uit te voeren, maar op zich niet gemakkelijk te begrijpen is. Na deze beschrijving werd de uitvoer van het betreffende graafalgoritme gevisualiseerd met behulp van een voorbeeldgraaf. We kunnen opmerken dat, dankzij deze visualisatie, het dan gemakkelijker werd om de uitvoering van een algoritme te leren begrijpen.

\chapter{Doelstellingen}
In het vorige hoofdstuk is een uitleg gegeven over het nut van het visualizeren van het verloop van een algoritme. Dit kan zeer behulpzaam zijn indien men het verloop van een algoritme beter wenst te begrijpen dan men doet door enkel haar (pseudo-) code te zien. Het visualizeren van een algoritme wensen we dus te automatiseren door een programma, dat liefst geschikt is voor zo veel mogelijk verschillende graafalgoritmes.

Nu is het doel van deze sectie enkele doelstellingen te genereren waar een dergelijke automatisatie aan zou moeten voldoen.

\begin{itemize}
\item Elk mogelijk type graaf voorstellen.
\item Een zo bruikbaar, maar nog steeds algemeen mogelijke interface bieden voor het werken met grafen.
\item Wijzigingen in de structuur van de graaf kunnen weergeven. (Zie de laatste afbeeldingen in figuur~\ref{AlgKruskal:Exec}, dergelijke wijzigingen willen we kunnen zien).

Nu is de vraag, wat hebben zoveel mogelijk graafalgoritmes gemeen met elkaar, op zo'n manier dat het in de doelstellingen opgenomen kan worden; de vorige drie punten zijn uiteraard nog slechts erg mager. Als we de algoritmen in figuur~\ref{Alg:Path} en figuur~\ref{Alg:Kruskal} met elkaar vergelijken kunnen we opmerken dat de voortgang van het algoritme in beide gevallen in een soort van lijst type bijgehouden wordt. Vandaar de vierde doelstelling:
\item Een zo algemeen mogelijk lijst-type aanbieden aan de gebruiker en de informatie die hieruit gewonnen kan worden weer kunnen geven.

Tussen deze algoritmen zijn verder geen grote algemeenheden meer te vinden. Echter, om toch nog iets meer bruikbaarheid aan te kunnen bieden maken we een vijfde doelstelling:
\item Aan de gebruiker toelaten tijdens de voortgang van het algoritme een willekeurige knoop of boog te markeren. Indien de eerste vier doelstellingen niet genoeg zijn om het verloop van een algoritme degelijk te tonen, kan op z'n minst de gebruiker hier zelf nog enigszins aan sleutelen.
\item Bijhouden hoe veel de gebruikte structuren gequeried worden, zodat de gebruiker een beeld krijgt van de complexiteit van het algoritme.
\end{itemize}

\chapter{Gebruik}\label{section:Gebruik}
Dit deel van dit verslag zal handelen rond hoe dit project gebruikt dient te worden. Eerst zal er uitgelegd worden hoe het gecompileerd kan worden. Vervolgens wordt het gebruik van dit project voor de visualisatie van een daadwerkelijk algoritme uitgelegd. Dit gedeelte zal voldoende ge\"illustreerd worden aan de hand van voorbeelden.
\section{Installatie van het project}
Dit thesisproject is afhankelijk van enkele libraries. Deze zijn QtGui en QtCore\cite{qt:download}. Een afhankelijk die minder duidelijk is is het GraphViz\cite{graphviz:download} project, van welke de DOT\cite{graphviz:dot} tool gebruikt wordt om een Graaf te kunnen tonen. Het dot commando behoort in het path beschikbaar te zijn.

\subsection{Installatie onder linux}
Voor linuxgebruikers is er bij dit project een compile script toegevoegd: \emph{compile.sh}. Deze zal eerst het project als library compileren en installeren. Hiervoor kunnen administratorrechten gevraagd zijn. Zodra dit voltooid is wordt de applicatie op zich gecompileerd. Tot slot worden alle plugins in de plugin map ook gecompileerd.

De locatie waar dit project ge\"installeerd wordt is standaard `/usr/local/lib/' en `/usr/local/include/graafalgoritmes/'. Dit kan gewijzigd worden in \emph{graafalgoritmes\_lib.pro}, maar in alle andere .pro files moet dan wel het includepath aangepast worden.

\subsection{Installatie onder windows}
Ook voor windowsgebruikers is er een compile script toegevoegd\footnote{In het bijgeleverde script wordt een standaard-installatie verondersteld. Het dient aangepast te worden indien dit niet het geval is.}. Dit is \emph{compile.bat}. Dit handelt geheel analoog aan het linux equivalent. De gebruiker zal echter wel waarschijnlijk het installatiepad willen aanpassen. Standaard zou dit terecht komen in `C:/usr/local/'.

De installatie dient uitgevoerd te worden in de opdrachtprompt (\emph{cmd.exe}). Tijdens de installatie moet men zich ervan verzekeren dat de Qt libraries zich in het path bevinden. Bij een standaard Qt installatie wordt dit niet gedaan. Best kan dit dus in de door Qt bijgeleverde `Qt Command Prompt' gedaan worden. In dit geval moet men wel manueel de locatie van de DOT tool aangeven voor de uitvoering van het programma op zich. Dit kan gedaan worden door een ander script \emph{adjustPathForWindows.bat} aan te roepen. Dit zal het path uitbreiden met de standaardlocatie van de DOT tool en het bestand \emph{graafalgoritmes\_app.exe} in de map \emph{debug} uitvoeren.

\section{Opbouwen van een graaf}\label{Usage:Graph}
Er zijn twee mogelijkheden om een graaf in het programma te laden. Een eerste laat toe om dit hard-coded te doen, een tweede laat toe om een graaf in te lezen van een file.

\subsection{Hard-coded}
Om een graaf in de code aan te maken hoort men te beginnen door een instantie van de Graph klasse aan te maken. De constructor voor deze klasse aanvaard \'e\'en parameter \function{bool directed}, welke aangeeft of dit ofwel een gerichte, ofwel een ongerichte graaf is.

Zodra een graaf aangemaakt is kunnen hier knopen aan toegevoegd worden. Gezien we deze knopen later nodig hebben om paden aan te kunnen maken behoren deze tijdelijk opgeslagen te worden als locale variabele. De syntax voor het aanmaken van een knoop is \function{Graph::createNode( int identifier )} of ook \function{Graph::createNode( QString label, int identifier = \dots )}. Deze functies geven de zojuist gecre\"eerde knoop terug. In de eerste variant wordt de gebruiker verwacht een unieke identifier voor deze knoop te voorzien. In het tweede geval kan de gebruiker de knoop een label geven en eventueel een identifier specifi\"eren ofwel het systeem deze \'e\'en toe laten wijzen. Gezien deze functies aangeroepen worden op de graaf waarmee men werkt, worden deze meteen toegevoegd.

Zodra de gewenste knopen toegevoegd of tenminste aangemaakt zijn, kan de gebruiker beginnen paden aan te maken. Zoals eerder vermeld hebben we hier de eerder aangemaakte knopen voor nodig. De syntax voor de creatie van een pad is \function{Graph::createEdge( Node from, Node to, QString label = "", int identifier = ... )}. De eerste twee parameters zijn dus de begin en eind knoop. In het geval van een ongerichte graaf maakt de volgorde hier niet veel uit. De derde parameter is een optioneel label dat aan het pad gegeven kan worden. Tot slot, zoals bij de knopen, kan er een identifier aan het pad gegeven worden. Indien dit veld leeggelaten wordt wijst het systeem hier een vrije identifier aan toe. Na de creatie van een pad kan deze aan de graaf toegevoegd worden met de functie \function{Graph::addEdge( Edge edge )}.

Aan de hand van de zojuist gespecifi\"eerde functies kan een graaf volledig opgebouwd worden. Voorbeeldcode is gegeven in appendix~\ref{Code:Graph}.

\subsection{Inladen van file}
Een tweede mogelijkheid voor het inladen van een graaf in het geheugen is door dit in te laden van een file. Dit is zeer simpel. Enkel de statische functie \function{Graph::fromFile( const char *filename )} hoeft aangeroepen te worden en deze functie zal netjes een pointer naar de zojuist aangemaakte \class{Graph} teruggeven.

De syntax van de file vanwaar een graaf ingeladen zou moeten worden is heel simpel. In de file is commentaar toegelaten door een hele regel achter \function{//} te zetten. Lege regels zijn alsook toegelaten. Als een van de eerste regels zal een gebruiker \function{directed=true} ofwel \function{directed=false} willen gebruiken om aan te geven of het hier om een gerichte ofwel een ongerichte graaf gaat.

Op dit punt kunnen we, zoals in de hard-coded methode, knopen en paden toe gaan voegen. Een knoop wordt toegevoegd door een statement als \function{Node( int id )} of \function{Node( int id, string label )} toe te voegen. In dit geval is de gebruiker er volledig voor verantwoordelijk om aan iedere knoop een unieke identifier te geven. Deze identifier zal later nodig zijn om paden toe te voegen. Een label is uiteraard optioneel.

Om een pad toe te voegen kan een statement \function{Edge( int nodeFrom, int nodeTo, string label )} of \function{Edge( int nodeFrom, int nodeTo )} toegevoegd worden. De eerste twee parameters zijn de identifiers behorende bij de eerder toegevoegde knopen. De laatste parameter, het label, is volledig optioneel.

Dit is alles wat benodigd is om een volledige graaf in te kunnen laden. Een vlug voorbeeld van hoe dit er dan precies uit zal zien wordt gegeven in appendix~\ref{Code:File}

\section{Creatie van een algoritme}
Voor de visualisatie van een algoritme is het uiteraard essenti\"eel op een specifieke manier een algoritme te voorzien. In dit project zal het vereist zijn een klasse aan te maken die overerft van de \class{Algorithm} klasse.

Ten eerste zal de implementatie van deze \class{Algorithm} klasse besproken worden. Later wordt het gebruik in meer detail uitgelegd. Ten eerste moet de constructor van de basisklasse aangeroepen worden. Als parameter krijgt deze een \class{Graph$*$} mee, dus is dit tenminste \'e\'en parameter die de overervende klasse ook zal moeten hebben. Er wordt verondersteld dat de \class{Graph} al volledig ge\"initialiseerd is op het moment dat de constructor aangeroepen wordt.

In de \class{Algorithm} klasse is er \'e\'en puur virtuele functie die ge\"implementeerd dient te worden. Dit is \function{void Algorithm::run()}. Het aanroepen van deze functie wordt verondersteld de uitvoering van het gehele algoritme als resultaat te hebben.

Dit is echter niet genoeg voor een degelijke visualizatie van het geheel. Alhoewel er geprobeerd is op een zo natuurlijk mogelijke manier data over de uitvoering van het algoritme te verkrijgen zal de gebruiker enige klassen moeten gebruiken voor een beter resultaat. Uiteraard heeft de gebruiker toegang tot de \class{Graph} die aan de constructor meegegeven is. Deze is toegankelijk door de functie \function{Graph* Algorithm::graph()const} aan te roepen. Dankzij het gebruik van deze \class{Graph} kan het aantal queries op deze klasse bijgehouden worden, wat de gebruiker een beeld van de complexiteit van het algoritme kan geven.

Verder is er een \class{Container} klasse voorzien. Deze klasse is een soort front-end voor een lijststructuur die \class{ContainerElement$*$}en bevat. Een \class{ContainerElement} kan een \class{Node}, een \class{Edge}, een \class{int}, een \class{double} en een \class{QString} bevatten. In het kort is dus het grootste deel van alle mogelijke soorten data die een gebruiker zou kunnen willen bijhouden in een soort lijststructuur in deze \class{Container}s op te slaan. Het is aan de gebruiker hier een duidelijk overzicht over te houden.

In de constructor van het \class{Algorithm} kan de gebruiker enige malen de functies \function{Algorithm::containerAdd()} en \function{Algorithm::containerPop()} aanroepen, welke respectievelijk aan het einde van deze lijst van \class{Container}s \'e\'en toevoegt ofwel \'e\'en verwijdert. Via \function{int Algorithm::containerCount() const} kan het aantal containers opgevraagd worden en via \function{Container \&Algorithm::container( int i ) const} kan toegang tot deze containers verkregen worden.

Tot slot, als dit nog niet voor genoeg data zorgt om op een degelijke manier een algoritme te visualizeren, kan de gebruiker ook de functies \function{Algorithm::highlight( const Node \&node )} en \function{Algorithm::highlight( const Edge \&edge )} aanroepen. Deze functies zullen, tot deze actie overschreven is, de betreffende \class{Node} of \class{Edge} een andere kleur geven.

Een implementatie van een algoritme wordt gedemonstreerd in appendix~\ref{Code:Algorithm}.

\section{Creatie van een algoritme als plugin}\label{Info:Plugin}
Een algoritme kan ook als plugin aan het project toegevoegd worden. Hiervoor is ten eerste de standaard implementatie van een algoritme benodigd, zoals beschreven in de vorige sectie. De plugin zelf zal gedefini\"eerd worden door een andere klasse. Deze klasse moet afgeleid worden van \class{QObject} en \class{AlgorithmInterface}. De statements \function{Q\_OBJECT} en \function{Q\_INTERFACES(AlgorithmInterface)} moeten in de definitie van deze klasse opgenomen worden.

Om tot een werkende plugin te komen, moet men drie pure virtuele functies implementeren: \function{Algorithm *createAlgorithm( Graph *g )}, \function{QString name()const} en \function{bool canAcceptGraph( Graph *g )}. De eerste functie moet een instantie van het algoritme teruggeven. De tweede zal de naam teruggeven en de laatste mag enkele testen bevatten waarmee men zich er van kan verzekeren dat het weigert uitgevoerd te worden op een graaf die niet aan de vereisten voldoet. Een voorbeeld hiervan is dat het algoritme van Kruskal zoals beschreven in figuur~\ref{AlgKruskal:Exec} op pagina~\pageref{AlgKruskal:Exec} een graaf mag weigeren indien deze geen gewichten op de paden heeft gedefini\"eerd.

Tot slot moet aan de bodem van de file het statement \function{Q\_EXPORT\_PLUGIN2(algNAAM\-plugin, NAAMPlugin) } toegevoegd worden. Naam moet hier uiteraard veranderd worden naar de naam van het algoritme waarvoor men een plugin maakt. In de \emph{plugin} map zijn voorbeelden hiervan te vinden, alsook de .pro files die gebruikt worden om deze te compileren.

Een voorbeeld van een plugin vindt men in appendix~\ref{Code:Plugin}.

\section{Visualisatie van het algoritme}
Nu zijn we op het punt dat we zowel een graaf als een algoritme klaar hebben. Het enige dat ons nog rest is dit algoritme te tonen. Dit is simpeler dan de vorige stappen. De gebruiker hoeft enkel een \class{Visualizer} klasse aan te maken en \function{Visualizer::addAlgorithm( Algorithm * a )} aan te roepen. Als dit algoritme dan uitgevoerd wordt (door \function{Algorithm::run()} aan te roepen), zal data over dit algoritme weergegeven worden. Belangrijk is wel op te merken dat er een \class{QApplication} in de main functie aangemaakt moet worden. Uiteraard, want dit project gebruikt de Qt libraries voor de GUI. Dit wordt gedemonstreerd in appendix~\ref{Code:Visualizer}.

\section{Visualisatie van een plugin}
Indien een plugin voor het algoritme geschreven is en deze plugin zich in de \emph{plugins} folder bevindt, kan men dit algoritme visualiseren door de applicatie zelf uit te voeren. Onder `Algorithm' in de linkerbovenhoek hoort dan de naam van het algoritme gevonden te kunnen worden. Dit wordt getoond in figuur~\ref{App:Plugin}.

\ctable[pos=h!t, figure, botcap, caption={Plugin}, label={App:Plugin}]{c}{}{\includegraphics[scale=1]{images/app_plugin.png}}

\section{Gebruik van het programma}
Het gebruik van het programma zelf zal met enkele screenshots toegelicht worden. Indien men het programma opstart, ziet men het scherm in figuur~\ref{App:Interface1}.

\ctable[pos=h!t, figure, botcap, caption={Interface}, label={App:Interface1}]{c}{}{\includegraphics[scale=.5]{images/interface/interface1.png}}

Om iets te hebben om te visualizeren dient een algoritme geselecteerd te worden. Hiervoor klikt men op het `Algorithm' menu en ziet men een lijst van algoritmen die als plugin geselecteerd zijn. Zodra een algoritme gekozen is (hier: Prim's Algoritme) ziet men het scherm in figuur~\ref{App:Interface2}.

\ctable[pos=h!t, figure, botcap, caption={Interface}, label={App:Interface2}]{c}{}{\includegraphics[scale=.5]{images/interface/interface2.png}}

Nu hebben we een algoritme gekozen, maar nog geen graaf om dit om uit te voeren. Om een graaf te selecteren klikt men op `Graph', dan `Choose...', en selecteert men het bestand waarin de gewenste graaf gedefini\"eerd is\footnote{Voorbeeldgrafen vindt men in de plugins map.}. De geselecteerde graaf wordt getoond en u wordt om bevestiging gevraagd. Na de bevestiging krijgt het algoritme de kans deze graaf te weigeren. Indien dit niet gebeurt, ziet u het scherm in figuur~\ref{App:Interface3}.

\ctable[pos=h!t, figure, botcap, caption={Interface}, label={App:Interface3}]{c}{}{\includegraphics[scale=.5]{images/interface/interface3.png}}

Nu is alle benodigde informatie klaar om een visualizatie van het gekozen algoritme op de gekozen graaf te starten. Men klikt op `Show', en het scherm zoals in figuur~\ref{App:Interface4} zal verschijnen.

\ctable[pos=h!t, figure, botcap, caption={Interface}, label={App:Interface4}]{c}{}{\includegraphics[scale=.35]{images/interface/interface4.png}}

Nu kan men ofwel door play en stop, ofwel door step, stap voor stap de uitvoering van het algoritme bekijken. Een voorbeeld van wat u tegen zal komen in het geval van het Algoritme van Prim op de eerder getoonde graaf wordt getoond in figuur~\ref{App:Interface5}.

\ctable[pos=h!t, figure, botcap, caption={Interface}, label={App:Interface5}]{c}{}{\includegraphics[scale=.35]{images/interface/interface5.png}}

In figuur~\ref{App:Interface5} merkt men ten eerste de markeringen op de graaf op. Bij het algoritme van Prim stellen deze de edges en nodes voor die in de minimum spanning tree opgenomen worden. Duidelijk zijn er nog nodes niet gemarkeerd, dit algoritme is nog niet voltooid.

Aan de rechteronderkant ziet men `Container 0'. Hier wordt de inhoud van de gebruikte container gezien. Grofweg stelt dit de voortgang van het algoritme voor. Deze container zal uiteindelijk de gehele minimum spanning tree bevatten. Tot slot kan men aan de rechterbovenkant `Graph Access' herkennen. Hier wordt bijgehouden hoeveel queries er precies op de graaf uitgevoerd worden.



\chapter{Werking}\label{section:Werking}
In dit hoofdstuk zal overlopen worden hoe dit project in grote lijnen functioneert. Er zal besproken worden hoe de klassen opgebouwd zijn, wat hun doel is, en hoe zij bijdragen tot het groter geheel. Grotendeels zal dit besproken worden in volgorde van afhankelijkheid van andere klassen, beginnende bij de klassen die van weinig andere klassen afhangen. Ook zullen eerst de meer datagerichte klassen aan bod komen, waar later bondig de eerder GUI-gerichte klassen ook besproken worden.

\section{Action}
Een module die geheel onafhankelijk is van de rest van het project is de \class{Action} module. Deze module is hoofzakelijk verantwoordelijk voor communicatie doorheen dit project. Vele klassen hebben weet nodig van de \class{Action} klassen, omdat ze deze benutten om door te kunnen geven wat er precies gebeurt.

\subsection{ActionCommunicator}
De eerste specifieke klasse om kort te bespreken is de \class{ActionCommunicator}. Zoals de naam doet vermoeden is dit een pure communicatieklasse. Een pointer naar zo een object zal aan de later te bespreken \class{Action} klassen doorgegeven worden. Deze klassen kunnen functies op dit object aanroepen. Gezien de \class{ActionCommunicator} van \class{QObject} overerft, kan deze dan een signaal emitten om aan te geven welk resultaat er gewenst wordt. Een voorbeeld van een dergelijk signaal is \function{void ActionCommunicator::nodeRemove( int nodeID )}, welke aan de GUI-gerichte klassen door zal geven dat er een node uit de graaf verwijderd werd.
\ctable[pos=h!t, figure, botcap, caption={ActionCommunicator}, label={Dia:ActionCommunicator}]{c}{}{\includegraphics[scale=.35]{images/ActionCommunicator.png}}

De functies die beschikbaar zijn in de \class{ActionCommunicator} zijn getoond in figuur~\ref{Dia:ActionCommunicator}.

\subsection{Action klassehi\"erarchie}
De laatste klasse die besproken zal worden voor deze module is de \class{Action}. Wanneer een van de interne objecten binnen dit project aan wilt geven dat er een bepaalde actie op dit object uitgevoerd wordt, zal het een object dat overerft van \class{Action} cre\"eren en dit via een signaal doorgeven.\footnote{Het maximaal aantal ontvangers voor een dergelijk signaal is \'e\'en. Voordat het daadwerkelijk ge-emit wordt, wordt er altijd getest of er wel tenminste een object is dat dit signaal op zal vangen. Als dit niet het geval is wordt het \class{Action} object gedelete.}

Eerder werd vermeld dat het hier om een \emph{klassehi\"erarchie}, niet gewoon een simpele klasse, gaat. Voor iedere actie die er uitgevoerd kan worden\footnote{Sommige acties zullen opgesplitst worden over meerdere \class{Action} klassen.}, zal er een klasse zijn die van \class{Action} overerft en deze actie zal voorstellen. Een voorbeeld hiervan is, om het vorige voorbeeld voort te zetten, de \class{NodeRemoveAction}.

Een belangrijke functie die door elke \class{Action} klasse geherimplementeerd behoort te worden is \function{void Action::exec( ActionCommunicator* )}. Zodra deze functie aangeroepen wordt, zal de \class{Action} klasse aan de \class{ActionCommunicator} doorgeven welke actie er precies door voorgesteld wordt.

Een versimpeld klassediagram voor de \class{Action} is te zien in figuur~\ref{Dia:Action}.

\ctable[pos=h!t, figure, botcap, caption={Action}, label={Dia:Action}]{c}{}{\includegraphics[scale=.35]{images/Action.png}}

Het grote verschil tussen al deze subklassen (van welke slechts twee getoond zijn) is de implementatie van \function{void Action::exec( ActionCommunicator* )}. Als voorbeeld wordt de implementatie van \function{void NodeAddAction::exec( ActionCommunicator* )} in listing~\ref{Code:Action} getoond. Duidelijk is dat het enige dat in deze functie gedaan wordt is functies op \class{ActionCommunicator} aanroepen, die op hun beurt een signaal verzenden naar een hogere klasse die dit zal interpreteren.

\begin{lstlisting}[caption={Action}, label={Code:Action}]
void NodeAddAction::exec( ActionCommunicator *communicator ){
	communicator->addNode( QString().setNum(m_nodeID) + QString( " [label=\"" ) + m_nodeLabel + QString("\"];") );
}
\end{lstlisting}

Een volledig overzicht van de \class{Action} klassen is te zien in figuur ~\ref{Dia:ActionInheritance} in appendix~\ref{ActionInheritance}.

\section{Graph}
Het hart van het project is uiteraard de \class{Graph} module. Dit is de klasse die de gebruiker van het project zal moeten benutten om een graaf voor te stellen. Alvorens nodes en edges te kunnen maken, behoort een graph te bestaan waar deze aan toegevoegd dienen te worden, vandaar zal eerst de \class{Graph} klasse zelf behandeld worden, daarna de \class{Node} en \class{Edge}.

\subsection{Graph}
De \class{Node} en \class{Edge} klassen liggen aan de basis voor de \class{Graph}, de klasse die de gebruiker regelmatig zal moeten queryen en updaten. Het gebruik van de \class{Graph} klasse is al in grote mate aan bod gekomen in sectie~\ref{Usage:Graph}. Buiten een interface en gebruiksobject voor de eindgebruiker te zijn, is de \class{Graph} klasse ook verantwoordelijk voor het rapporteren van queries op de graaf.

In de klasse \class{Graph} is er een functie \function{void Graph::report( Action* )} voorzien die na zal kijken of er een receiver is voor het bijbehorende signaal. Als dit het geval is, zal het signaal verzonden worden. Is dit niet het geval, dan wordt het \class{Action} object gedelete. Vele van de functies die op een \class{Graph} aangeroepen kunnen worden, zoals bijvoorbeeld \function{Node Graph::node( int i )}, zullen deze aanroepen om bijvoorbeeld aan te geven dat een element van deze \class{Graph} aangeroepen is. Men mag opmerken dat \class{Graph} wel signalen verzendt, maar zelf niets opvangt en bijhoudt. Dit gebeurt pas later in de \class{Algorithm} module.

Belangrijk aan de hele \class{Graph} module is dat al deze klassen een \function{QString(List) toDOT() const} functie hebben. Zodra deze functie aangeroepen wordt op een \class{Graph}, wordt verwacht dat de \class{Graph} een DOT\cite{graphviz:dot} representatie teruggeeft van de graaf. Door de code zal dit eenmalig aangeroepen worden om de initi\"ele graaf weer te kunnen geven, maar indien de graaf verandert tijdens het algoritme, is het mogelijk dit meerdere malen aan te roepen. De \class{Node} en \class{Edge} klasse implementeren dergelijke functies ook en geven precies \'e\'en regel in de DOT taal terug, die binnen een graafdefinitie te gebruiken is. 

Het klassediagram voor de \class{Graph} klasse is te zien in figuur~\ref{Dia:Graph}.

\ctable[pos=h!t, figure, botcap, caption={Graph}, label={Dia:Graph}]{c}{}{\includegraphics[scale=.35]{images/Graph.png}}

De constructor van de \class{Graph} neemt slechts \'e\'en argument, deze bepaalt of er ofwel een gerichte of een ongerichte graaf gecre\"eerd wordt. De \function{add} functies zullen ofwel een \class{Node} ofwel een \class{Edge} achteraan in de respectievelijke \class{QList} toevoegen. Er is gekozen om de graaf te defini\"eren door een lijst van nodes en een lijst van edges om de implementatie zo bruikbaar mogelijk te behouden. Een matrix-implementatie, bijvoorbeeld, laat niet toe dat er twee paden van de een naar de andere node zijn. Het gebruik van een adjacency list implementatie\cite[p.~207]{cursus}
had een mogelijkheid geweest, maar deze is enkel performant voor dunne grafen. Ook hier is het ongepast ons op \'e\'en soort graaf te richten.

Er zijn meerdere mogelijkheden voorzien om de elementen van de graaf te kunnen queryen.

\begin{lstlisting}[caption={node( int i )}, label={Code:node()}]
Node Graph::node( int i )const{
	//Er wordt gerapporteerd dat er een query op een node gedaan is
	report( new NodeAccessAction( m_nodes[i].identifier() ) );
	
	//En deze node wordt gereturnd.
	return m_nodes[i];
}
\end{lstlisting}

\clearpage
\begin{lstlisting}[caption={nodeWithId( int i )}, label={Code:nodeWithId()}]
Node Graph::nodeWithId(int i, bool *ok)const{
	if( ok )
		*ok = true;
		
	//Doorzoek de nodes
	for( int j = 0; j < m_nodes.size(); j++ ){
		//Totdat de juiste gevonden is
		if( m_nodes[j].identifier() == i ){
			//Rapporteer een query
			report( new NodeAccessAction(i) );
			return m_nodes[j];
		}
	}
	
	//Geef aan dat er geen dergelijke node bestaat
	//en return een 'willekeurige knoop'.
	if(ok)
		*ok = false;
	return m_nodes[0];
}
\end{lstlisting}

In listings~\ref{Code:node()} en~\ref{Code:nodeWithId()} zijn twee mogelijke manieren getoond om de graaf voor een \class{Node} te queryen. De eerste (\function{node( int i )}), zal de \class{Node} teruggeven die als i-de is toegevoegd. Deze functie is vooral bedoeld gebruikt te worden om de lijst met nodes te doorlopen. De tweede functie (\function{nodeWithId( int i )}) zal gegarandeerd, als deze bestaat, de \class{Node} teruggeven die de gespecifi\"eerde identifier heeft. Merk op dat als de nodes van $0$ tot $n-1$ genummerd zijn en in die volgorde zijn toegevoegd, beide functies precies hetzelfde resultaat geven. Buiten dit wordt in beide functies eenmaal \function{\_report( NodeAccessAction* )} aangeroepen, om aan te geven dat er eenmalig een node bezoekt is.

De functies \function{QList<Node> GraphImp::neighboursOf( const Node \&node )}, \function{QList<Node> GraphImp::reachableFrom( const Node \&node )} en \function{QList<Edge> GraphImp::edgesFrom( const Node \&node )} werken vrijwel identiek. Hun werking wordt ge\"illustreerd in listing~\ref{Code:reachableFrom()}.

\begin{lstlisting}[label={Code:reachableFrom()}, caption={reachableFrom( const Node \&node )}]
//Geeft alle nodes terug die te bereiken zijn vanuit de bronknoop.
QList<Node> Graph::reachableFrom( const Node &node ){
	//We geven de knopen terug in de vorm van een lijst
	QList<Node> ret;
	for( unsigned int i = 0; i < numEdges(); i++ ){
		//Alle edges worden doorlopen. We slaan ze op in een lokale variabele om de graaf slechts eenmaals te hoeven queryen.
		const Edge &e = edge(i);
		//Als de edge vertrekt in de bron...
		if( e.from() == node )
			ret.push_back( e.to() );
		//Als de graaf ongericht is en aankomt in de bron...
		else if( !isDirected && e.to() == node )
			ret.push_back( e.from() );
	}
	return ret;
}
\end{lstlisting}

Zoals te zien in listing~\ref{Code:reachableFrom()} worden voor de eerder vermelde functies alle paden doorlopen. Als deze voldoen aan de criteria van de query, worden deze teruggegeven in de vorm van een lijst. Op te merken is dat de functie \function{Edge Graph::edge( int i )} hier gebruikt wordt, in plaats van de lijst direct aan te spreken. Deze querys zijn van complexiteit O(n), waar n het aantal paden van de graaf is, en door de aanroep naar \function{Edge Graph::edge( int i )} zal er dus ook n maal \function{\_report( EdgeAccessAction* )} aangeroepen worden.

Een volgende zeer belangrijke functie is \function{QStringList Graph::toDOT()const}. Deze functie is er verantwoordelijk voor een lijst van strings terug te geven die, indien ze aan elkaar geplakt wordt met newlines als seperators, een geldige string over de DOT taal is.

\begin{lstlisting}[label={Code:toDOT()}, caption={toDOT()}]
//De functie die de representatie van de graaf teruggeeft.
QStringList Graph::toDOT()const{
	QStringList result;
	
	//Specifieer of de graaf ofwel gericht ofwel ongericht is.
	if( m_isDirected )
		result.push_back( "digraph{" );
	else
		result.push_back( "graph{" );
	
	//Voeg de representaties van de nodes en edges to
	_nodesToDOT( result );
	_edgesToDOT( result );
	
	//En we sluiten de accolade.
	result.push_back( "}" );
	return result;
}

//De functie die de representaties van de knopen teruggeeft.
void GraphImp::_nodesToDOT( QStringList &result )const{
	//Later parsen we deze output zelf. Dit commentaar wordt in die parser verwacht.
	result.push_back( "/*nodes*/" );
	
	//Voeg de Node::toDOT toe. Deze functie was eerder besproken.
	for( unsigned int i = 0; i < numNodes(); i++ )
		result.push_back( m_nodes[i].toDOT() );
}

//De functie die de representaties van de paden teruggeeft.
void GraphImp::_edgesToDOT( QStringList &result )const{
	//Later parsen we deze output zelf. Dit commentaar wordt in die parser verwacht.
	result.push_back( "/*edges*/" );
	
	//Voeg de Edge::toDOT toe. Deze functie was eerder besproken.
	for( unsigned int i = 0; i < numEdges(); i++ )
		result.push_back( m_edges[i].toDOT(m_isDirected) );
}
\end{lstlisting}

In listing~\ref{Code:toDOT()} wordt de \function{toDOT} functie getoond. In feite is dit een zeer simpele string operatie. In commentaar was aangegeven dat deze output later, in een andere module, geparsed wordt. Wetende dat het parsen van een enigszins ingewikkelde string niet de meest effici\"ente manier van communicatie is, is hier toch voor gekozen om zo min mogelijk onderlinge afhankelijkheid tussen klassen van verschillende modules te behouden.

Uiteindelijk is er ook de \function{void Graph::fromFile( const char *file )} functie, die het mogelijk maakt een graaf vanuit een text file in een bepaald formaat in te lezen. Dit formaat wordt beschreven in appendix \ref{Code:File} op pagina \pageref{Code:File}. De functie zelf wordt niet getoond, aangezien dit slechts een simpele parsing van een string bevat. Lijn per lijn wordt de file gelezen en ge\"interpreteerd.

Tot slot is de functie \function{EdgeList Graph::operator[](int i)const} te vinden. Indien \function{graph} een graaf is en \function{graph[i][j]} aangeroepen wordt, zal deze aanroep de identifier van het eerst gevonde pad teruggeven tussen de knopen met identifiers \function{i} en \function{j}. Als deze niet bestaat zal $-1$ teruggegeven worden. Deze functie wordt getoond in listing~\ref{Code:EdgeList}.

\begin{lstlisting}[label={Code:EdgeList}, caption={EdgeList}]
EdgeList GraphImp::operator[](int i)const{
	//We geven een EdgeList terug waarop nogmaals operator[] op aangeroepen zal worden. Deze klasse moet weten of het om een gerichte ofwel een ongerichte graaf gaat.
	EdgeList ret( m_isDirected );
	
	//Alle edges worden doorlopen.
	for( int j = 0; j < m_edges.size(); j++ ){
		const Edge &e = edge(j);
		
		//De edge moet teruggegeven worden als zij begint in knoop i, ofwel de graaf ongericht is en zij aankomt in knoop i.
		if( e.from().identifier() == i || (!m_isDirected && e.to().identifier() == i) )
			ret.add(e);
	}
	return ret;
}

//Geeft de identifier terug van de eerste edge die gevonden wordt die aankomt in knoop met identifier i.
int EdgeList::operator[](int i)const{
	//We doorlopen de edges die eerder teruggegeven werden.
	for( int j = 0; j < m_edges.size(); j++ ){
	
		if( m_isDirected ){//Als de graaf gericht is moet de edge aankomen in i
			if( m_edges[j].to().identifier() == i )
				return m_edges[j].identifier();
		}else{//Als deze ongericht is moet de edge in i aankomen of vertrekken
			if( m_edges[j].from().identifier() == i || m_edges[j].to().identifier() == i )
				return m_edges[j].identifier();
		}
	}
	return -1;
}
\end{lstlisting}


\subsection{Node}
De basis van een graaf is uiteraard de knoop, vandaar de \class{Node} klasse. Deze klasse stelt precies \'e\'en knoop voor. Als members heeft zij een label en een identifier. Het label is hier optioneel en kan leeg zijn. Iedere Node zelf zal een unieke identifier moeten bevatten. Optioneel kan de gebruiker deze zelf specifi\"eren. Een nieuwe knoop met een eerder gebruikte identifier is enkel te cre\"eren door deze te kopi\"eren van een knoop die deze al gebruikt. Het klassediagram van de \class{Node} is te zien in figuur~\ref{Dia:Node}.

\ctable[pos=h!t, figure, botcap, caption={Node}, label={Dia:Node}]{c}{}{\includegraphics[scale=.25]{images/Node.png}}

In het klassediagram is op te merken dat er geen public constructors zijn buiten de copy-constructor. Nodes dienen aangemaakt te worden door de \class{Graph} waarin ze toegevoegd gaan worden. De reden hiervoor is \class{Node}s \class{Graph}-specifieke identifiers te kunnen geven, welk op zich een taak van de \class{Graph} behoort te zijn. De constructors worden getoond in listing~\ref{Code:createNode}.

\begin{lstlisting}[caption={createNode()}, label={Code:createNode}]
Node Graph::createNode( int identifier = -1 ){
	//Indien geen ID gespecifiëerd, vragen we die aan.
	if( identifier < 0 )
		identifier = _getNewNodeIdentifier();
	
	//Als de identifier ongeldig is, vragen we een nieuwe.
	if( !_registerNodeIdentifier( identifier ) ){
		identifier = _getNewNodeIdentifier();
		_registerNodeIdentifier(identifier);
	}
	
	//Maak de knoop aan, voeg ze toe aan de graph en return ze.
	Node n(identifier);
	addNode(n);
	return n;
}

Node Graph::createNode( QString label, int identifier = -1 ){
	//Indien geen ID gespecifiëerd, vragen we die aan.
	if( identifier < 0 )
		identifier = _getNewNodeIdentifier();
	
	//Als de identifier ongeldig is, vragen we een nieuwe.
	if( !_registerNodeIdentifier( identifier ) ){
		identifier = _getNewNodeIdentifier();
		_registerNodeIdentifier(identifier);
	}
	
	//Maak de knoop aan, voeg ze toe aan de graph en return ze.
	Node n(label, identifier);
	addNode(n);
	return n;
}
\end{lstlisting}

In beide functies in listing~\ref{Code:createNode} is op te merken dat deze functies enkel dienen om de identifier variabele een geldige waarde te geven. Het gebruik van deze identifiers wordt getoond in listing~\ref{Code:nodeIdentifier}.
\clearpage
\begin{lstlisting}[label={Code:nodeIdentifier}, caption={identifier}]
//Functie voor aanvraag van een ongebruikt ID
int Graph::_getNewNodeIdentifier(){
	//Deze lijst behoort ten allen tijden gesorteerd te zijn.
	qSort(m_nodeIdentifiers);

	//Indien leeg, geven we 0 terug.
	if( m_nodeIdentifiers.size() == 0 )
		return 0;
	
	//Anders, de hoogst gebruikte ID plus 1.
	return m_nodeIdentifiers.back()+1;
}

//Functie voor registratie van een ID
bool Graph::_registerNodeIdentifier( int identifier ){
	//We verzekeren ons ervan dat de ID niet gebruikt wordt.
	for( int i = 0; i < m_nodeIdentifiers.size(); i++ )
		if( m_nodeIdentifiers[i] == identifier )
			return false;
	
	//En voegen deze toe aan de gebruikte IDs.
	m_nodeIdentifiers.push_back( identifier );
	return true;
}
\end{lstlisting}

Het identifier systeem is zeer belangrijk om toch zeker verschillende knopen van elkaar te kunnen onderscheiden. Een klasse als de \class{Node} zelf heeft geen weet van de \class{Graph} waarin ze terecht zal komen, vandaar dat dit in \class{Graph} verzorgd wordt.

Een laatste functie om op te merken is \function{QString Node::toDOT()const}. Deze functie wordt gebruikt om output te genereren om deze knoop te tonen in de DOT taal van GraphViz. In dit geval is het genoeg om in \'e\'en regel haar identifier en optioneel het label terug te geven.

\subsection{Edge}
Zodra we knopen hebben kunnen we deze verbinden met bogen, vandaar de \class{Edge} klasse. Deze klasse heeft vier belangrijke members, twee knopen (van en naar), een label en een identifier. Dit label mag uiteraard weer leeg zijn. Voor de identifier geldt dezelfde redenering als eerder voor de knopen. Het klassediagram van de \class{Edge} is te zien in figuur~\ref{Dia:Edge}.
\clearpage
\ctable[pos=h!t, figure, botcap, caption={Edge}, label={Dia:Edge}]{c}{}{\includegraphics[scale=.35]{images/Edge.png}}

De functie \function{QString Edge::toDOT( bool isDirected )const} is weer aanwezig. Zoals bij de \class{Node} geeft deze in \'e\'en regel een string terug die de identifiers van de knopen die het verbindt bevat, haar optionele label, in welke de identifier van de \class{Edge} zelf verborgen wordt. Voor de contructor geldt ook weer hetzelfde als voor de \class{Node}; deze wordt getoond in listing~\ref{Code:createEdge}.

\begin{lstlisting}[caption={createEdge}, label={Code:createEdge}]
Edge Graph::createEdge( Node from, Node to, QString label, int identifier ){
	if( identifier < 0 )
		identifier = _getNewEdgeIdentifier();
	
	if( !_registerEdgeIdentifier(identifier) ){
		identifier = _getNewEdgeIdentifier();
		_registerEdgeIdentifier(identifier);
	}
	
	Edge e( from, to, label, identifier );
	addEdge(e);
	return e;
}
\end{lstlisting}

In listing~\ref{Code:createEdge} merken we duidelijk de analogie op met de constructors voor de \class{Node} klasse. Vandaar ook dat het identifiersysteem voor de \class{Edge} niet verder toegelicht zal worden. Het is volledig analoog.

\section{Algorithm}
De \class{Algorithm} module is zeer belangrijk in het data-extractie deel van dit project. Deze module biedt de gebruiker enerzijds een interface om een algoritme zo gebruiksvriendelijk als mogelijk te implementeren en probeert anderzijds zoveel mogelijk informatie over dit algoritme te verzamelen in de vorm van \class{Action}s.

Voor het data-extractie gedeelte gebruikt de \class{Algorithm} klasse \class{Container}s, die op zich opgebouwd zijn uit \class{ContainerElement}en.

\subsection{ContainerElement}
De eerste klasse om te bespreken is het \class{ContainerElement}. Dit is een zeer simpele klasse die niets anders dan een entry in een lijst voor moet stellen, flexibel genoeg om de meeste soorten data te ondersteunen die door een gebruiker in een lijst gezet zouden kunnen worden. Deze klasse biedt geen functionaliteit, buiten de access functies voor haar member variabelen. Haar klassediagram wordt getoond in figuur~\ref{Dia:ContainerElement}.

\ctable[pos=h!t, figure, botcap, caption={ContainerElement}, label={Dia:ContainerElement}]{c}{}{\includegraphics[scale=.35]{images/ContainerElement.png}}

In figuur~\ref{Dia:ContainerElement} kan met meteen opmerken dat \class{ContainerElement} afhankelijk is van \class{Action}. Dit is ook noodzakelijk. \function{set} functies, zoals \function{ContainerElement* ContainerElement::setNode( const Node \&node )}, zullen een \class{Action} moeten emitten om aan te geven dat de inhoud van het \class{Container} gewijzigd is. Meer expliciet is dit getoond in listing~\ref{Code:setNode()}.

\begin{lstlisting}[caption={setNode( const Node \&node )}, label={Code:setNode()}]
ContainerElement *ContainerElement::setNode( const Node &node ){
	if( m_node != 0 )
		delete m_node;
	m_node = new Node( node );
	_report( new ContainerElementSetNodeAction(0, 0, node.identifier(), node.label()) );
	return this;
}
\end{lstlisting}

De code in listing~\ref{Code:setNode()} is redelijk voordehandliggend. Zoals eerder aangegeven wordt er inderdaad een \class{Action} uitgezonden. Iedere \function{set} functie zal een pointer naar het huidige object teruggeven. Dit laat constructies zoals \function{element -> setNode(node) -> setEdge(edge);} toe. De implementatie van de \function{\_report()} functie wordt getoond in listing~\ref{Code:_report()}.
\clearpage
\begin{lstlisting}[caption={\_report( Action* )}, label={Code:_report()}]
void ContainerElement::_report( ContainerElementAction *action ){
	//Als er iemand naar dit signaal luistert...
	if( receivers(SIGNAL(reportAction(ContainerElementAction*))) > 0 ){
		//Dan verzenden we dit signaal.
		emit reportAction(action);
	//Anders...
	}else{
		//Deleten we de action, er luistert toch niemand.
		delete action;
	}
}
\end{lstlisting}

De \function{\_report()} functie getoond in listing~\ref{Code:_report()} zal in meerdere klassen onder licht aangepaste vormen terugkomen. Deze functie is strikt noodzakelijk om geen memory-leaks te introduceren. De overige functies zijn verder niet echt interessant en zullen niet verder toegelicht worden.

\subsection{Container}
De \class{ContainerElement} klasse wordt gebruikt in de \class{Container} klasse. Deze klasse herimplementeert een standaard soort lijst klasse en heeft de verantwoordelijkheid om de bovenliggende klassen van veranderingen op de hoogte te houden. Haar klassediagram wordt getoond in figuur~\ref{Dia:Container}.

\ctable[pos=h!t, figure, botcap, caption={Container}, label={Dia:Container}]{c}{}{\includegraphics[scale=.35]{images/Container.png}}

Het getoonde klassediagram is in alle waarschijnlijkheid niet zeer verassend. Er zijn uiteraard functies voorzien, zoals \function{void Container::push\_front( ContainerElement* )}, die precies in de STL, of de Qt klassen, ook voorzien zijn. De reden voor de herimplementatie wordt getoond in listing~\ref{Code:push_front()}.
\clearpage
\begin{lstlisting}[label={Code:push_front()}, caption={push\_front( ContainerElement* )}]
//Voeg een nieuw element aan de voorkant van de lijst toe.
void Container::push_front( ContainerElement *element ){
	//Ten eerste voegen we het daadwerkelijk toe...
	m_container.push_front( element );
	
	//..dan rapporteren we aan hogere klassen dat we een nieuw element hebben...
	_reportNewElement( element, 0 );
	
	//...en we zetten communicatie met dit element op.
	connect( element, SIGNAL(reportAction(ContainerElementAction*)), this, SLOT(_reportChild(ContainerElementAction*)) );
}
\end{lstlisting}

In listing~\ref{Code:push_front()} zien we dat er inderdaad meteen een aanroep gedaan wordt naar \function{void QList<ContainerElement*>::push\_front( ContainerElement* )}. We merken echter ook op dat er weer een call naar een \function{\_report()} functie gedaan wordt. Uiteindelijk willen we ook dat het nieuwe \class{ContainerElement} met ons kan communiceren, vandaar de verbinding van het signaal. De implementatie van het slot dat zojuist verbonden werd, wordt getoond in listing~\ref{Code:_reportChild()}.

\begin{lstlisting}[caption={\_reportChild( ContainerElementAction* )}, label={Code:_reportChild()}]
void Container::_reportChild( ContainerElementAction *action ){
	//Van wie komt dit signaal?
	QObject *s = sender();
	//Zodra we de afzender geidentificeerd hebben...
	for( int i = 0; i < m_container.size(); i++ )
		if( m_container[i] == s )
			//Vullen we ontbrekende informatie aan.
			action->setElement(i);
	//En het signaal wordt weer verder doorgestuurd.
	_report(action);
}
\end{lstlisting}

Zoals gedemonstreerd in listing~\ref{Code:_reportChild()}, kent het \class{ContainerElement} haar volgnummer niet op het moment dat het een \class{Action} verstuurt. Vandaar dat deze koppelfunctie noodzakelijk is om de missende gegevens aan te vullen.

De \function{\_report()} functie die we hier zien is eerder getoond in listing~\ref{Code:_report()}. Nieuw is echter wel de functie \function{\_reportNewElement()}. In het kort zal deze enkel meerdere \class{Action}s tegelijkertijd versturen, namelijk \class{ContainerElementAddAction} en \\ \class{ContainerElementSetNodeAction}\footnote{En andere verwandte \class{Action}s.} indien noodzakelijk.

\subsection{Algorithm}
De \class{Algorithm} klasse biedt een interface voor de creatie van een algoritme. Belangrijk in deze klasse is de \function{virtual void run()} functie die de gebruiker dient te herimplementeren. Ook bevat deze klasse de access en creatie functies voor het \class{Container} systeem.

Meer specifiek bevat zij pointers naar de huidige \class{Graph} en \class{Container}s. Waar alle bovengenoemde klassen \class{Action}s uitzenden, worden deze in \class{Algorithm} opgevangen in een queue. Belangrijk is dat deze klasse een functie \function{Action* \_popAction()} biedt. Deze zal gebruikt worden door de gui klassen om \'e\'en specifiek \class{Action} object te verkrijgen, welk dan gevisualizeerd dient te worden. Haar klassediagram wordt getoond in figuur~\ref{Dia:AlgorithmImp}.

\ctable[pos=h!t, figure, botcap, caption={Algorithm}, label={Dia:AlgorithmImp}]{c}{}{\includegraphics[scale=.35]{images/Algorithm.png}}

Meteen is op te merken dat de \class{Algorithm} zowel \class{Container}s als een \class{Graph} bevat. Zodra deze toegevoegd worden aan deze klasse, zullen hun signalen verbonden worden met de slots waarin deze passen. Dit wordt ge\"illustreerd in listing~\ref{Code:containerAdd()}, waar de signalen van een container gekoppeld worden aan onze eigen slots.

\begin{lstlisting}[label={Code:containerAdd()}, caption={containerAdd()}]
void Algorithm::containerAdd(){
	m_containers.push_back( Container() );
	connect( &m_containers[m_containers.size()-1], SIGNAL(reportAction(ContainerElementAction*)), this, SLOT(_reportAction(ContainerElementAction*)) );
}
\end{lstlisting}

De functie aanroep naar \function{\_reportAction( ContainerElementAction* )} heeft hetzelfde nut als de eerder beschreven functie \function{\_reportChildAction( ContainerElementAction* )}, dewelke getoond was in listing~\ref{Code:_reportChild()}. De \class{Container} van welke dit signaal komt heeft uiteraard ook geen kennis van haar eigen volgnummer. Tot slot zal de eigen functie\footnote{Een slot.} \function{void \_report( Action* )} de ontvangen signalen opslaan in een lijst die als queue gebruikt zal worden.

Later kan een andere klasse de functie \function{Action *\_popAction()} aanroepen om toegang tot deze informatie te krijgen.

\subsection{AlgorithmInterface}
De \class{AlgorithmInterface} dient om een plugin van af te leiden. Deze plugin zal van de \class{AlgorithmInterface} afgeleid moeten worden en haar functies moeten implementeren. Meer informatie werd gegeven in hoofdstuk~\ref{Info:Plugin} op pagina~\pageref{Info:Plugin}. Haar klassediagram wordt getoond in figuur~\ref{Dia:AlgorithmInterface}.

\ctable[pos=h!t, figure, botcap, caption={AlgorithmInterface}, label={Dia:AlgorithmInterface}]{c}{}{\includegraphics[scale=.35]{images/AlgorithmInterface.png}}

Men kan meteen opmerken dat \class{AlgorithmInterface} een pure abstracte klasse is. Ze bevat slechts vier functies, die ieder door de gebruiker ge\"implementeerd dienen te worden. Op zich heeft deze klasse geen functie en wordt niet gebruikt.

\section{DOT}
De DOT module heeft als functionaliteit de representatie van een graaf te beheren. De klasse die hiervoor verantwoordelijk is, is de \class{DManager} klasse. Deze wordt ge\"initialiseerd met de uitvoer van \function{QStringList Graph::toDOT()const}, en later door kleine calls als resultaat van de verkregen \class{Action}s wordt haar inhoud gewijzigd. Zonder de DOT module zou de representatie van de graaf direct als string gemanipuleerd moeten worden, wat het resultaat oneindig ingewikkeld zou maken. Deze module versimpeld dit door hi\"erarchisch tewerk te gaan.

\subsection{DCommonData}
\class{DCommonData} dient als een basisklasse voor \class{DNodeData} en \class{DEdgeData}. Beiden stellen ofwel een knoop ofwel een boog voor. De belangrijkste functionaliteit van \class{DCommonData} is het bijhouden van een lijst van opties voor de weergave van het respectievelijke element dat het representeert. Haar klassediagram wordt getoond in figuur~\ref{Dia:DCommonData}.

\ctable[pos=h!t, figure, botcap, caption={DCommonData}, label={Dia:DCommonData}]{c}{}{\includegraphics[scale=.35]{images/DCommonData.png}}

Het eerste dat men op kan merken zijn de member variabelen \function{m\_options} en \function{m\_values}. Deze lijsten stellen een serie van opties an hun respectievelijke waarden voor. Alle opties die hier gegeven zijn worden verwacht geldige opties over de DOT taal te zijn. Tot slot is er ook de variabele \function{m\_colourStack}, die de eventuele gewenste kleur van het gegeven object aan haar top zal bevatten, ofwel leeg zal zijn. Als voorbeeld kan er de waarde ``red'' op een moment aan de top staan, waarna de functie \function{Algorithm::highlight( Node* )} aangeroepen kan worden en de top van de stack de waarde ``green'' krijgt. Als deze highlight ongedaan gemaakt zou worden, is het wenselijk dat de gegeven Node weer ``red'' aan de top van de stack zal hebben.

De belangrijkste functie van deze klasse is de \function{void setOption( QString option, QString value )} functie. Deze zal, indien aanwezig, de waarde van de gespecifi\"eerde optie aanpassen, of anders zowel de waarde als de optie aan beide lijsten toevoegen.

Haar overige functies zijn allemaal om strings te parsen, en dus niet interessant on hier te bespreken.

\subsection{DEdgeData}
\class{DEdgeData} is de representatie van een boog. Als belangrijkste functionaliteit heeft deze klasse een \function{QString toDOT( bool directed )const} functie. Deze geeft de DOT representatie van deze boog terug.

\subsection{DNodeData}
\class{DNodeData} is in functionaliteit bijna gelijk aan \class{DEdgeData}. Het is niet nodig deze klasse verder te bespreken.

\subsection{DManager}
\class{DManager} is de klasse met de daarwerkelijke verantwoordelijkheid de representatie van de graaf te bewaren. Als members heeft zij een begin- en eindstring waarmee de representatie van de graaf in de DOT taal zal beginnen. Verder bevat zij alle \class{DNodeData} en \class{DEdgeData} objecten, die de graaf voorstellen.

De \class{DManager} wordt ge\"initialiseerd door een DOT representatie als \class{QStringList} aan de constructor mee te geven. Deze wordt geparsed en hier wordt informatie over de specifieke bogen en knopen uit gewonnen.

De \class{DManager} bevat ook een instantie van een \class{ActionCommunicator} object dat eerder besproken is. Dit is nodig, omdat vele signalen van deze \class{ActionCommunicator} door de \class{DManager} (en klassen op hoger niveau) opgevangen dienen te worden.

Deze klasse heeft twee zeer relevante functies. Ten eerste is er \function{QString toDOT()const}, welke alle data over de graaf, inclusief wijzigingen, terug om zal zetten in een geldige string over de DOT taal. Ten tweede is er de functie \function{QPixmap toQPixmap()const}, welke een visuele representatie van de graaf terug zal geven. Deze functie zal \function{toDOT()} aanroepen en de output neerschrijven in een tijdelijk bestand. Op dit bestand wordt het dot commando uitgevoerd en wordt er een tijdelijk beeldbestand aangemaakt. Dit beeldbestand wordt in de \class{QPixmap} ingeladen en alle tijdelijke bestanden worden verwijderd.

Bovengenoemde werkwijze kan ingewikkeld en rommelig lijken. Er is echter toch zeer bewust voor deze aanpak gekozen, omdat er op deze manier geen code-afhankelijkheid is met het GraphViz project. De enige code-afhankelijkheid op dit moment is van de Qt klassen. De dot tool zal echter \emph{wel} op het systeem ge\"installeerd moeten zijn.


\section{Visualizer}
De \class{Visualizer} module bestaat grotendeels uit GUI klassen die niet verder besproken zullen worden. In een main functie dient een \class{Visualizer} aangemaakt te worden om een algoritme mee te kunnen visualizeren. Op deze klasse dient \function{void addAlgorithm( Algorithm* a )} aangeroepen te worden. Meerdere algoritmes kunnen op deze wijze naast elkaar gevisualizeerd worden.

\section{Het geheel}
Wat er op dit moment not niet volledig besproken is, is hoe precies de \class{Action} klasse doorheen het project doorgegeven en gebruikt wordt. Het simpelst is om dit te beschouwen in twee delen, data extractie en data visualizatie. Een diagram om dit te illustreren is getoond in figuur~\ref{Dia:ActionUsage}\footnote{Weergegeven klassen GraphImp en AlgorithmImp zijn ondertussen hernoemd naar respectievelijk Graph en Algorithm.}.

\ctable[pos=h!t, figure, botcap, caption={Action doorheen het project}, label={Dia:ActionUsage}]{c}{}{\includegraphics[scale=.35]{images/ActionUsage.png}}

\subsection{Data Extractie}
Het data extractie gedeelte is in dit document al redelijk veel aan bod te komen. Om het nogmaals op te sommen werkt dit als volgt. In de klassen \class{ContainerElement}, \class{Container} en \class{GraphImp} kunnen er onder zekere omstandigheden signalen verzonden worden die als parameter een \class{Action}, of afgeleid object bevatten. Deze worden verder naar boven toe doorgegeven tot ze uiteindelijk belanden in de \class{AlgorithmImp}. Hier worden ze bewaard tot later, door de functie \function{Action* popAction()} aan te roepen, deze verder doorgegeven kunnen worden.

\subsection{Data visualizatie}
De daadwerkelijke visualizatie van deze \class{Action}s is op dit moment nog niet geheel duidelijk.

Door een callback van de GUI kan de \class{AlgorithmVisualizer} op \class{AlgorithmImp} de functie \function{Action* AlgorithmImp::popAction()} aanroepen. Op haar beurt zal de \class{AlgorithmVisualizer} op de \class{GraphVisualizer} de functie \function{void GraphVisualizer::update( Action* )} aanroepen. De \class{GraphVisualizer} zal dan uiteindelijk \function{void Action::exec( ActionCommunicator* )} aanroepen. Dit leidt er toe dat de \class{Action} klasse de \class{ActionCommunicator} zal manipuleren, als reactie waarop de \class{Action\-Communicator} signalen zal verzenden. Deze signalen worden in GUI klassen opgevangen en getoond. De \class{GraphVisualizer} zal eventueel de \class{DManager} manipuleren om een vernieuwing van de graaf tot gevolg te hebben.

\chapter{Visualizaties}\label{section:Visualizaties}
In dit hoofdstuk zullen enkele visualizaties met behulp van dit project weergegeven worden. Voor elk bijgeleverd algoritme zal in diepte besproken worden hoe dit precies functioneert en is ge\"implementeerd, met uiteraard het bijbehorend resultaat.

\section{Prim's Algoritme}
\subsection{Probleemstelling}
Gegeven een gewogen graaf zonder `losse' knopen. Vindt de minimale omspannende boom voor deze graaf. De minimale omspannende boom is een boom die alle knopen van de originele graaf bevat en deze verbindt met knopen van welke het totale gewicht het kleinst mogelijk is.\cite[p.~227]{cursus}

\subsection{Algoritme}
Het algoritme dat dit probleem oplost kan beschreven worden als volgt:

\begin{lstlisting}[language={}, label={Alg:Prim}, caption={Prim's Algoritme}]
Initialiseer de op te bouwen MST als de lege boom; initialiseer een verzameling knopen $U$ als een singleton bestaande uit een willekeurige knoop van de graaf.
Zoek een goedkoopste boog tussen een knooppunt in $U$ en een knooppunt buiten $U$. Voeg deze boog toe aan de op te bouwen MST en voeg het knooppunt buiten $U$ toe aan $U$.
Herhaal stap 2 totdat $U$ alle knopen van de graaf bevat.
\end{lstlisting}

\subsection{Implementatie}
De MST zal ge\"implementeerd worden door een container. Het eerste element zal \'e\'en enkele knoop zijn, verder zal ieder element zowel de laatst toegevoegde knoop zijn, als de boog de gebruikt werd om deze te verbinden. Om redenen van effici\"entie zal een een boolean array gebruikt worden om  $U$ voor te stellen, zelf al is dit ook van de gebruikte container af te lezen.

In pseudo-code zal dit algoritme ge\"implementeerd worden zoals in listing~\ref{Pseudo:Prim}.

\begin{lstlisting}[language={}, label={Pseudo:Prim}, caption={Pseude implementatie Prim's Algoritme}]
Gebruik %\'e\'en) Container $cont$.
Gebruik een array van booleans $seen$ met grootte $n$ en initialiseer deze op false.
Voeg node 0 toe aan $cont$ en zet $seen[0]$ op $true$.

Zo lang het ons lukt om knopen toe te voegen aan $cont$...
	Noem $e_{min}$ de minimale Edge.
	
	Voor alle edges...
		Indien $e_{min}$ al gedefinieerd is en de kost van $e$ groter is dan $e_{min}$...
			Sla deze edge $e$ over en ga verder in 8.
		
		Indien de huidige edge $e$ van een knoop in $seen$ vertrekt en in een knoop buiten $seen$ aankomt (of andersom)...
			$e_{min}=e$
	
	Indien $e_{min}$ gedefinieerd is...
		Voeg $e_{min}$ toe aan $cont$, alsook de knoop die nog niet in $seen$ gemarkeerd was.
		Zet $seen$ op $true$ voor de toegevoegde knoop.

Ieder element van $seen$ is nu $true$.
$cont$ bevat de gezochte MST.
\end{lstlisting}

Dit algoritme kan dan ge\"implementeerd worden zoals in listing~\ref{Code:Prim}. Voor alle duidelijkheid is de pseudo-code van listing~\ref{Pseudo:Prim} aan deze code toegevoegd als commentaar.

\begin{lstlisting}[label={Code:Prim}, caption={Implementatie Prim's Algoritme}]
AlgPrim::AlgPrim( Graph *g ): Algorithm( g ){
	//We zullen een container gebruiken.
	containerAdd();
}

AlgPrim::~AlgPrim(){
	
}

void AlgPrim::run(){
	//Initialisatie. Hier wordt Container &cont gebruikt voor gemak.
	Container &cont = container(0);
	cont.push_back( (new ContainerElement)->setNode(graph()->node(0)) );
	
	int n = graph()->numNodes();
	
	bool *seen = new bool[n];
	for( int i = 0; i < n; i++ )
		seen[i] = false;
	seen[0] = true;
	
	bool success = true;
	
	//Zolang het ons lukt om knopen toe te voegen...
	while( success ){
	
		//We veronderstellen dat dit niet lukt.
		success = false;
		
		//i is de positie van $e_{min}$ in de graaf, min is de kost.
		int i = -1;
		int min = -1;
		
		//Voor alle edges...
		for( int j = 0; j < graph()->numEdges(); j++ ){
			const Edge &e = graph()->edge(j);
			
			//Indien $e_{min}$ al gedefinieerd is en de kost van $e$ groter is dan $e_{min}$...
			if( success && e.label().toInt() >= min )
				continue;
			
			//Indien de huidige edge $e$ van een knoop in $seen$ vertrekt en in een knoop buiten $seen$ aankomt
			if( seen[e.from().identifier()] && !seen[e.to().identifier()] ){
			
				//$e_{min}=e$
				success = true;
				min = e.label().toInt();
				i = j;
			
			//of andersom
			}else if( seen[e.to().identifier()] && !seen[e.from().identifier()] ){
			
				//$e_{min}=e$
				success = true;
				min = e.label().toInt();
				i = j;
			}
		}
		
		//Indien $e_{min}$ gedefinieerd is...
		if( success ){
			const Edge &e = graph()->edge(i);
			
			//Voeg $e_{min}$ toe aan $cont$, alsook de knoop die nog niet in $seen$ gemarkeerd was.
			//Zet $seen$ op $true$ voor de toegevoegde knoop.
			if( seen[e.from().identifier()] ){
				cont.push_back( (new ContainerElement)->setNode(e.to())->setEdge(e) );
				seen[e.to().identifier()] = true;
			}else{
				cont.push_back( (new ContainerElement)->setNode(e.from())->setEdge(e) );
				seen[e.from().identifier()] = true;
			}
		}
	}
	
	//Ieder element van $seen$ is nu $true$.
	//$cont$ bevat de gezochte MST.
	
	//Als demonstratie verwijderen we nu alle edges die niet in de MST zitten.
	
	//Voor alle edges...
	for( int i = 0; i < graph()->numEdges(); i++ ){
		const Edge &e = graph()->edge(i);
		
		//Indien ze niet in de MST zit...
		bool shouldKeep = false;
		for( int j = 1; j < cont.size() && !shouldKeep; j++ )
			shouldKeep = e == *cont[j]->edge();
		
		if(!shouldKeep){
			//Verwijder ze.
			graph()->removeEdge(e);
			i--;
		}
	}
}

\end{lstlisting}

\subsection{Visualizatie}
De visualizatie van het verloop van dit algoritme zal dan gaan als volgt.

\ctable[pos=h!t, figure, botcap, caption={Prim's Algoritme}, label={AlgPrim:exec1}]{c}{}{\includegraphics[scale=.5]{images/AlgPrim/AlgPrim1.png}}

In figuur~\ref{AlgPrim:exec1} ziet men de startgraaf. Het algoritme is ge\"initialiseerd met knoop $0$ (label $A$) toegevoegd aan $cont$. Men merkt op dat er op dit moment \'e\'en query op de graaf is gebeurd om knoop $0$ te selecteren.

\ctable[pos=h!t, figure, botcap, caption={Prim's Algoritme}, label={AlgPrim:exec2}]{c}{}{\includegraphics[scale=.5]{images/AlgPrim/AlgPrim2.png}}

In de vorige figuur kon men twee paden van knoop $0$ zien. Het pad met de laagste kost, pad $0\rightarrow 3$, is in figuur~\ref{AlgPrim:exec2} toegevoegd aan $cont$. Men merkt op dat er op dit moment twaalf maal een query op de graaf is gebeurd om de edges te doorlopen. De graaf heeft 11 edges, en er is \'e\'en extra query gebeurd om de $e_{min}$ toe te voegen aan $cont$.

\ctable[pos=h!t, figure, botcap, caption={Prim's Algoritme}, label={AlgPrim:exec3}]{c}{}{\includegraphics[scale=.5]{images/AlgPrim/AlgPrim3.png}}

In figuur~\ref{AlgPrim:exec3} wordt het programma getoond na afloop van het eigenlijke algoritme. Men kan opmerken dat er op dit moment 72 queries op de edges van de graaf gebeurd zijn. Dit is gelijk aan $6\times 12$ ofwel $(n-1) \times (\#edges+1)$. Men kan zien dat $cont$ nu daadwerkelijk de MST bevat. Elke knoop van de graaf is hier aan toegevoegd en ze zijn allen met elkaar verbonden. De inhoud van $cont$ is rood gemarkeerd op de graaf.

\ctable[pos=h!t, figure, botcap, caption={Prim's Algoritme}, label={AlgPrim:exec4}]{c}{}{\includegraphics[scale=.5]{images/AlgPrim/AlgPrim4.png}}

Figuur~\ref{AlgPrim:exec4} toont het programma na afloop van het totale algoritme. Hier wordt enkel de MST nog getoond; alle overige edges zijn nu verwijderd.

\clearpage
\section{Warshall's Algoritme}
\subsection{Probleemstelling}
Gegeven een gerichte graaf. Vind de transitieve sluiting van deze graaf. De transitieve sluiting van een graaf bevat een boog tussen twee knopen, telkens als er in de originele graaf een pad tussen de twee knopen is.\cite[p.~219]{cursus}


\subsection{Algoritme}
Het algoritme dat dit probleem oplost kan beschreven worden als volgt:

\begin{lstlisting}[language={}, caption={Warshall's Algoritme}, label={Pseudo:Warshall}]
Noem de graaf $G$.
Noem $T$ haar transitieve sluiting.
Initialiseer $T$ als $G$.

Voor alle knopen $k$ in $G$...
	Voor alle knopen $v$ in $G$...
		Voor alle knopen $w$ in $G$...
			Indien $T$ geen pad $v\rightarrow w$ bevat...
				Indien $v\rightarrow k$ en $k\rightarrow w$ in $T$ bestaan
					Voeg $v\rightarrow w$ toe aan $T$.
$T$ bevat nu de transitieve sluiting van $G$.
\end{lstlisting}

\subsection{Implementatie}
In de plaats van een aparte graaf te gebruiken voor de transitieve sluiting, zal direct op de graaf zelf gewerkt worden. Dit heeft geen invloed op het daadwerkelijke algoritme. Voor de implementatie is geen \class{Container} benodigd. De implementatie voor dit algoritme wordt getoond in listing~\ref{Code:Warshall}. Ook hier is grotendeels de pseudocode van listing~\ref{Pseudo:Warshall} toegevoegd als commentaar voor de duidelijkheid.

\begin{lstlisting}[label={Code:Warshall}, caption={Implementatie Warshall's Algoritme}]
AlgWarshall::AlgWarshall( Graph *g ): Algorithm( g ){
	
}

AlgWarshall::~AlgWarshall(){
	
}

void AlgWarshall::run(){
	
	//Voor alle nodes $k$...
	for( int k = 0; k < graph()->numNodes(); k++ ){
	
		//Voor alle nodes $v$...
		for( int v = 0; v < graph()->numNodes(); v++ ){
		
			//Voor alle nodes $w$...
			for( int w = 0; w < graph()->numNodes(); w++ ){
				
				//Indien $v\rightarrow w$ niet bestaat.
				if( (*graph())[v][w] < 0 ){
				
					//Als $v\rightarrow k$ en $k\rightarrow w$ bestaan
					if( (*graph())[v][k] >= 0 && (*graph())[k][w] >= 0 ){
					
						//Voeg $v\rightarrow w$ toe aan de graaf.
						graph()->createEdge(graph()->node(v), graph()->node(w));
						highlight( graph()->edge(graph()->numEdges()-1) );
					}
				}
			}
		}
	}
}
\end{lstlisting}

\subsection{Visualizatie}
Visualizatie van het verloop van dit algoritme zal dan gaan als volgt.

\ctable[pos=h!t, figure, botcap, caption={Warshall's Algoritme}, label={AlgWarshall:exec1}]{c}{}{\includegraphics[scale=.5]{images/AlgWarshall/AlgWarshall1.png}}

In figuur~\ref{AlgWarshall:exec1} ziet men de begingraaf voor dit algoritme.

\ctable[pos=h!t, figure, botcap, caption={Warshall's Algoritme}, label={AlgWarshall:exec2}]{c}{}{\includegraphics[scale=.5]{images/AlgWarshall/AlgWarshall2.png}}

In figuur~\ref{AlgWarshall:exec2} ziet men de eerste toegevoegde boog. Men merkt op dat er op dit moment al 201 edges gequeried zijn. Voor het eerst gevonden pad geldt: $k =  2, v = 5, w = 3$. Elke iteratie worden er tenminste 1, ten hoogste 4 edges gequeried, zoals in het algoritme te zien. Het is dus te verwachten dat dit aantal inderdaad zeer sterk stijgen zal.

\ctable[pos=h!t, figure, botcap, caption={Warshall's Algoritme}, label={AlgWarshall:exec3}]{c}{}{\includegraphics[scale=.5]{images/AlgWarshall/AlgWarshall3.png}}

In figuur~\ref{AlgWarshall:exec3} ziet men de tweede toegevoegde boog. Op dit moment zijn er 205 edges gequeried. Dit is niet veel meer dan in figuur~\ref{AlgWarshall:exec2}. Men kan opmerken dat geldt: $k =  2, v = 5, w = 4$.

\ctable[pos=h!t, figure, botcap, caption={Warshall's Algoritme}, label={AlgWarshall:exec4}]{c}{}{\includegraphics[scale=.5]{images/AlgWarshall/AlgWarshall4.png}}

Figuur~\ref{AlgWarshall:exec4} toont de eindsituatie van dit algoritme, de transitieve sluiting van de startgraaf. Alle toegevoegde paden zijn hier rood gemarkeerd.

\clearpage
\section{Floyd's Algoritme}
\subsection{Probleemstelling}
Gegeven een graaf. Zoek alle kortste paden tussen elk paar van twee knopen indien dit bestaat.\cite[p.~217]{cursus}

\subsection{Algoritme}
Het algoritme dat dit probleem oplost kan beschreven worden als volgt.

\begin{lstlisting}[language={}, caption={Floyd's algoritme}, label={Alg:Floyd}]
Gegeven graaf $G$.
Noem $T$ de resultaatgraaf.
Noem $P$ een graaf die de gebruikte paden bijhoudt.

Initialiseer $T$ als $G$.
Initialiseer $P$ met alle elementen $-1$.

Voor alle knopen $k\in T$...
	Voor alle knopen $v\in T$...
		Voor alle knopen $w\in T$...
			Indien kost($v\rightarrow k$ + $k\rightarrow w$) goedkoper dan kost($v\rightarrow w$)...
				T[v][w] = T[v][k] + T[k][w]
				P[v][w] = k
				
\end{lstlisting}


\subsection{Implementatie}
Om de visualizatie zo eenvoudig mogelijk te houden wordt de pad-graaf $P$ buiten beschouwing gelaten. Zoals bij het algoritme van Warshall gebruiken we de huidige graaf om $T$ te representeren. Dit kan geen kwaad, gezien de graaf $G$ in het algoritme enkel gebruikt wordt om $T$ te initialiseren.

Omdat de implementatie van een graaf zo algemeen mogelijk is gehouden, is het mogelijk dat er meerdere bogen tussen twee dezelfde knopen zijn. In het begin van het algoritme moeten deze dus verwijderd worden. Dit wordt gedaan door de code in listing~\ref{Code:Floyd1}. Dit is geen werkelijk deel van het bovenstaand beschreven algoritme, omdat dit algoritme het bestaan van dergelijke bogen vermijdt.

\begin{lstlisting}[caption={Floyd's Algoritme: Constructor}, label={Code:Floyd1}]
AlgFloyd::AlgFloyd( Graph *g ): Algorithm( g ){
	
	//Voor alle knopen $i\in g$...
	for( int i = 0; i < g->numNodes(); i++ ){
	
		//Voor alle bogen $j$ die in $i$ starten...
		QList<Edge> edges = g->edgesFrom( g->node(i) );
		for( int j = 0; j < edges.size(); j++ ){
			
			//Voor alle bogen $k$ die na $j$ in $i$ starten...
			for( int k = j+1; k < edges.size() && j >= 0; k++ ){
			
				//Indien dit een gerichte graaf is en beide bogen in dezelfde knoop aankomen
				if( g->isDirected() && edges[j].to() == edges[k].to() ){
				
					//Verwijder de duurste boog.
					if( edges[j].label().toInt() > edges[k].label().toInt() ){
						g->removeEdge(edges[j]);
						edges.takeAt(j);
						j--;
					}else{
						g->removeEdge(edges[k]);
						edges.takeAt(k);
						k--;
					}
				
				//Indien dit een ongerichte graaf is...
				}else if( !g->isDirected() ){
					int removeThis = -1;
					if( edges[j].from() == edges[k].from() && edges[j].to() == edges[k].to() ){
						removeThis = edges[j].label().toInt() > edges[k].label().toInt() ? j : k;
					}else if( edges[j].from() == edges[k].to() && edges[j].to() == edges[k].from() ){
						removeThis = edges[j].label().toInt() > edges[k].label().toInt() ? j : k;
					}
					
					//Indien beide bogen tussen dezelfde twee knopen zijn, verwijder de duurste.
					if( removeThis >= 0 ){
						g->removeEdge(edges[removeThis]);
						edges.takeAt(removeThis);
						if( removeThis == j )
							j--;
						else
							k--;
					}
				}
						
			}
		}
	}
}

\end{lstlisting}

Nu het geval van meerdere bogen tussen dezelfde twee knopen vermeden is, kan het algoritme relatief simpel geimplementeerd worden. Voor het gemak zal weer de pseudocode in het commentaar meegeleverd worden.

\begin{lstlisting}[caption={Implementatie Floyd's Algoritme}, label={Code:Floyd2}]
void AlgFloyd::run(){
	int n = graph()->numNodes();
	
	//Voor alle nodes $k$...
	for( int k = 0; k < n; k++ ){
	
		//Voor alle nodes $v$...
		for( int v = 0; v < n; v++ ){
		
			//Voor alle nodes $w$...
			for( int w = 0; w < n; w++ ){
			
				//Bereken de kosten
				const Edge *p;
				int costvk = cost(v,k);
				int costkw = cost(k,w);
				int costvw = cost(v,w, &p);
				
				//Indien kost($v\rightarrow k$ + $k\rightarrow w$) goedkoper dan kost($v\rightarrow w$)...
				if( costvk + costkw < costvw ){
				
					//Als er al een eerder pad bestond: verwijder dit.
					if( costvw < INFINITY )
						graph()->removeEdge( *p );
					
					//Als er geen werkelijk pad bestond, ga verder.
					if( costvk+costkw >= INFINITY )
						continue;
						
					//Voeg het pad met nieuwe kost toe aan de graaf.
					const Edge &e = graph()->createEdge( graph()->node(v), graph()->node(w), QString().setNum(costvk+costkw) );
					highlight(e);
				}
			}
		}
	}
}

//Bereken de kost van een pad $i\rightarrow j$ en geef eventueel het pad terug.
int AlgFloyd::cost( int i, int j, const Edge **e ){
	
	//Een pad $i\rightarrow i$ is gratis.
	if( i == j )
		return 0;
		
	//Indien er geen pad bestaat is de kost oneindig.
	int edgeID = (*graph())[i][j];
	if( edgeID < 0 )
		return INFINITY;
	
	const Edge &edge = graph()->edgeWithId(edgeID);
	if( e != 0 )
		*e = &edge;
	
	//Indien er een pad bestaat geven we haar kost terug.
	return edge.label().toInt();
}

\end{lstlisting}

\subsection{Visualizatie}
Visualizatie van het verloop van dit algoritme zal dan gaan als volgt.

\ctable[pos=h!t, figure, botcap, caption={Floyd's Algoritme}, label={AlgFloyd:exec2}]{c}{}{\includegraphics[scale=.5]{images/AlgFloyd/AlgFloyd2.png}}

Figuur~\ref{AlgFloyd:exec2} toont de startgraaf. Men kan hier meteen opmerken dat er al 25 queries op de edges zijn gedaan. Dit is vanwege de eerder besproken constructor.

\ctable[pos=h!t, figure, botcap, caption={Floyd's Algoritme}, label={AlgFloyd:exec3}]{c}{}{\includegraphics[scale=.5]{images/AlgFloyd/AlgFloyd3.png}}

In figuur~\ref{AlgFloyd:exec3} merken we duidelijk op dat er \'e\'en nieuw pad toegevoegd is. Dit stelt het pad $5\rightarrow 2\rightarrow 3$ voor.

\ctable[pos=h!t, figure, botcap, caption={Floyd's Algoritme}, label={AlgFloyd:exec4}]{c}{}{\includegraphics[scale=.5]{images/AlgFloyd/AlgFloyd4.png}}

In figuur~\ref{AlgFloyd:exec4} merken we op dat er precies \'e\'en iteratie later vijfmaal een edge gequeried is en tweemaal een knoop. Uit bovenstaande code is duidelijk dat er per iteratie ten minste 3 edges gequeried worden voor de kost. Indien een pad $i\rightarrow j$ bestaat zal de operatoe $cost( i, j )$ tweemaal naar een edge queryen. Eenmaals om het ID te achterhalen, andermaals om aan de edge zelf te komen.

\ctable[pos=h!t, figure, botcap, caption={Floyd's Algoritme}, label={AlgFloyd:exec5}]{c}{}{\includegraphics[scale=.5]{images/AlgFloyd/AlgFloyd5.png}}

In figuur~\ref{AlgFloyd:exec5} merkt men op dat er een pad uit de originele graaf verwijderd werd en een nieuwe toegevoegd. Het nieuwe pad $2\rightarrow 3\rightarrow 4$ in plaats van $2 \rightarrow 4$ is goedkoper gevonden.

\ctable[pos=h!t, figure, botcap, caption={Floyd's Algoritme}, label={AlgFloyd:exec6}]{c}{}{\includegraphics[scale=.5]{images/AlgFloyd/AlgFloyd6.png}}

Tot slot toont figuur~\ref{AlgFloyd:exec4} de eindsituatie.

\clearpage
\section{Dijkstra's Algoritme}
\subsection{Probleemstelling}
Gegeven een graaf, vindt het kortste pad van een bronknoop naar alle andere knopen in de graaf.\cite[p.~209]{cursus}

\subsection{Algoritme}
Volgend algoritme lost gegeven probleem op:

\begin{lstlisting}[language={}, caption={Dijkstra's Algoritme}, label={Alg:Dijkstra}]
Noem $G$ de graaf.
Neem $D$ een afstandsvector.
Neem $P$ een padvector.
Neem $S$ als verzameling van alle knopen.
Neem knoop $0$ als bronknoop.

Initialiseer alle elementen van $P$ op $0$ (de bronknoop).
Initialiseer alle elementen van $S$ op $false$. Zet $S[0]$ op $true$.

Voor alle knopen $k\in G$ doe...
	D[k] = G[0][k].

Voor $i$ van $1$ tot $n$, doe...
	Neem $w$ de knoop op minimale afstand van knoop $0$ waar $S[w] = false$.
	$S[w] = true$.
	
	Voor alle knopen $v$ in $G$, doe...
		Als (!S[v]) && D[v] > D[w] + G[w][v]..
			D[v] = D[w] + G[w][v].
			P[v] = w.

D bevat nu de afstand van de bronknoop naar alle andere knopen.
P bevat nu de paden genomen van de bronknoop naar alle andere knopen.
\end{lstlisting}

\subsection{Implementatie}
Om dit algoritme te implementeren zullen we \'e\'en container gebruiken. De inhoud van de container zal \'e\'en knoop en \'e\'en getal zijn. Dit getal is de afstand van de bronknoop die in het algoritme voorgesteld werd door $D$. De knoop zal de knoop zijn die in het algoritme voorgesteld werd door $P$ om het afgeledge pad bij te houden. Ook zullen we in deze zelfde container hier de boog toevoegen, zadat dat ook automatisch gehighlight wordt. Eerst wordt het aangepaste algoritme in pseudocode gegeven in listing~\ref{Pseudo:Dijkstra}.

\begin{lstlisting}[language={}, caption={Dijkstra's Algoritme}, label={Pseudo:Dijkstra}]
Neem $n$ het aantal knopen van $G$.
Neem $c$ de gebruikte container.
Neem $seen$ een boolean tabel grootte $n$.
Neem $source$ knoop $0$.

Initialiseer $c->knoop$ op $source$.
Initialiseer $c->int$ op oneindig, $c[0]->int$ op 0.
Initialiseer $seen$ op $false$, $seen[0]$ op $true$.

Voor alle paden $e$ vanuit $source$...
	Als $cost(e)$ < c->int...
		$c->int = cost(e)$
		$c->knoop = e->beginknoop$
		$c->boog = e$

Voor $i$ van $1$ tot $n$, doe...
	Neem $w$ de knoop op minimale afstand van knoop $0$ waar $seen[w] = false$.
	$seen[w] = true$.
	Voor alle knopen $v$ in $G$, doe...
		Als $!seen[v]$ en de c[v]->int > c[w]->int + G[w][v]...
			$c[v]->int = c[w]->int + G[w][v]$.
			$c[v]->node = w$.
			$c[v]->edge = w\rightarrow v$
\end{lstlisting}

Nu kan de pseudocode in listing~\ref{Pseudo:Dijkstra} gemakkelijk omgezet worden in een werkelijk algoritme. Dit wordt getoond in listing~\ref{Code:Dijkstra}.

\begin{lstlisting}[label={Code:Dijkstra}, caption={Dijkstra's Algoritme}]
//Constructor. Hier geven we enkel aan %\'e\'en) container te willen gebruiken.
AlgDijkstra::AlgDijkstra( Graph *g ): Algorithm( g ){
	containerAdd();
}

AlgDijkstra::~AlgDijkstra(){
	
}

void AlgDijkstra::run(){
	int n = graph()->numNodes();
	Container &c = container(0);
	bool seen[n];
	Node source = graph()->node(0);
	
	//In een loop initialiseren we de container en de seen tabel
	
	//Initialiseer alle elementen van $c$ op $0$ (de bronknoop).
	//Initialiseer alle elementen van $seen$ op $false$. Zet $seen[0]$ op $true$.
	
	for( int i = 0; i < n; i++ ){
		seen[i] = i == 0 ? true : false;
		c.push_back( new ContainerElement );
		c[i]->setNode(source);
		c[i]->setData( i == 0 ? 0 : INFINITY );
	}
	
	//Voor alle edges vanuit knoop 0..
	//	D[k] = G[0][k]
	
	QList<Edge> edgesFromSource = graph()->edgesFrom( source );
	for( int i = 0; i < edgesFromSource.size(); i++ ){
		int toID = edgesFromSource[i].to().identifier();
		int cost = edgesFromSource[i].label().toInt();
		if( c[toID]->dataInt() > cost ){
			c[toID]->setData(cost);
			c[toID]->setEdge(edgesFromSource[i]);
		}
	}
	
	//Voor $i$ van $1$ tot $n$, doe...
	for( int i = 1; i < n; i++ ){
	
		//Neem $w$ de knoop op minimale afstand van knoop $0$ waar $S[w] = false$.
		Node nodeW = min(c, seen);
		int w = nodeW.identifier();
		seen[nodeW.identifier()] = true;
		
		//Voor alle knopen $v$ in $G$, doe...
		for( int v = 0; v < n; v++ ){
			if( seen[v] )
				continue;
			
			int edgeWVid = (*graph())[w][v];
			if( edgeWVid < 0 )
				continue;
			
			Node nodeV = graph()->node(v);
			
			int distSourceV = c[v]->dataInt();
			
			const Edge &edgeWV = graph()->edgeWithId(edgeWVid);
			int distSourceWV = c[w]->dataInt() + edgeWV.label().toInt();
			
			//Als (!S[v]) && D[v] > D[w] + G[w][v]...
			if( distSourceV > distSourceWV ){
				c[v]->setData( distSourceWV );
				c[v]->setNode( nodeW );
				c[v]->setEdge( edgeWV );
			}
		}
	}
}

//Vind een knoop nog niet in $seen$ op minimale afstand van de bron
Node AlgDijkstra::min( Container &cont, bool seen[] ){
	int minCost = INFINITY;
	int minNode = 0;
	
	//Voor alle knopen $i$ in $G$...
	for( int i = 0; i < graph()->numNodes(); i++ ){
	
		//Als de knoop nog niet gezien is en tot nu toe dichtstbij...
		if( !seen[i] && cont[i]->dataInt() < minCost ){
			minCost = cont[i]->dataInt();
			minNode = i;
		}
	}
	return graph()->node(minNode);
}
\end{lstlisting}



\subsection{Visualizatie}

Visualizatie van het algoritme van Dijkstra zal dan gaan als volgt.

\ctable[pos=h!t, figure, botcap, caption={Dijkstra's Algoritme}, label={AlgDijkstra:exec1}]{c}{}{\includegraphics[scale=.4]{images/AlgDijkstra/AlgDijkstra1.png}}

Figuur~\ref{AlgDijkstra:exec1} toont de beginsituatie. Container $c$ is hier pas net ge\"initialiseerd.

\ctable[pos=h!t, figure, botcap, caption={Dijkstra's Algoritme}, label={AlgDijkstra:exec2}]{c}{}{\includegraphics[scale=.4]{images/AlgDijkstra/AlgDijkstra2.png}}

In een verder stadium van initialisatie zijn we in figuur~\ref{AlgDijkstra:exec2}. De paden vanuit de bron worden nu doorlopen. Het pad $0\rightarrow 1$ wordt hier gevonden. Gezien $7 < 999$, wordt dit toegevoegd.

\ctable[pos=h!t, figure, botcap, caption={Dijkstra's Algoritme}, label={AlgDijkstra:exec3}]{c}{}{\includegraphics[scale=.4]{images/AlgDijkstra/AlgDijkstra3.png}}

Figuur~\ref{AlgDijkstra:exec3} toont ons de situatie na de volledige initialisatie. Beide bogen vanuit de bron zijn nu toegevoegd.

\ctable[pos=h!t, figure, botcap, caption={Dijkstra's Algoritme}, label={AlgDijkstra:exec4}]{c}{}{\includegraphics[scale=.4]{images/AlgDijkstra/AlgDijkstra4.png}}

Figuur~\ref{AlgDijkstra:exec4} toont ons dat de $min$ functie hier knoop $3$ teruggaf. Deze knoop was nog niet in $seen$ (enkel $0$ op dit moment), en het dichtst bij de bron: $5 < 7$. Vandaar dat in deze stap $3\rightarrow 4$ toegevoegd wordt aan $c[4]$, dit is het kortste bekende pad waardoor deze knoop bereikt kan worden. Merk op dat $0\rightarrow 1\rightarrow 4$ korter is. Knoop $1$ is echter nog niet als $w$ knoop beschouwd.

\ctable[pos=h!t, figure, botcap, caption={Dijkstra's Algoritme}, label={AlgDijkstra:exec5}]{c}{}{\includegraphics[scale=.4]{images/AlgDijkstra/AlgDijkstra5.png}}

Figuur~\ref{AlgDijkstra:exec5} toont ons de situatie na afloop van het algoritme. Duidelijk is dat het eerder geselecteerde pad $3\rightarrow 4$ nu niet meer gebruikt wordt. Op de weergegeven graaf zelf wordt netjes getoond dat er vanuit iedere knoop slechts \'e\'en gemarkeerd (kortst) pad vanaf de bron is.







\appendix
\chapter{Action Inheritance}\label{ActionInheritance}

\ctable[pos=h!t, figure, botcap, caption={Action Inheritance}, label={Dia:ActionInheritance}]{c}{}{\includegraphics[scale=.25]{images/ActionInheritance.png}}

\chapter{Voorbeelden}
\section{Hard-coded constructie van een graaf}\label{Code:Graph}
\begin{lstlisting}[label={Code:makeGraph()}, caption={makeGraph()}]
Graph* makeGraph(){
	//Maak een nieuwe, gerichte graaf.
	Graph *graph = new Graph(true);
	
	//Maak drie nodes aan.
	const Node &node0 = graph->createNode();
	const Node &node1 = graph->createNode();
	const Node &node2 = graph->createNode();
	
	//Maak drie edges aan die deze knopen zullen verbinden.
	graph->createEdge(node0, node1);
	graph->createEdge(node1, node2);
	graph->createEdge(node2, node0);
	
	return graph;
}
\end{lstlisting}

\ctable[pos=h!t, figure, botcap, caption={Resultaat}]{c}{}{\includegraphics[scale=.5]{images/example_graph.png}}
\clearpage
\section{Graaf inladen van bestand}\label{Code:File}
\begin{lstlisting}[caption={Inladen van bestand}]
//gerichte graaf
directed=true

//Maak enkele knopen aan
Node(0)
Node(1)
Node(2)
Node(3)
Node(4)

//Verbind deze in een cirkel
Edge(0,1)
Edge(1,2)
Edge(2,3)
Edge(3,4)
Edge(4,0)

//Meer knopen
Node(5)
Node(6)
Node(7)
Node(8)
Node(9)

//Weer verbinden
Edge(5,6)
Edge(6,7)
Edge(7,8)
Edge(8,9)
Edge(9,5)

//Verbind beide cirkels
Edge(0,5)
Edge(1,6)
Edge(2,7)
Edge(3,8)
Edge(4,9)

\end{lstlisting}

\ctable[pos=h!t, figure, botcap, caption={Resultaat}, label={Graph:Example}]{c}{}{\includegraphics[scale=.35]{images/example_graph2.png}}
\clearpage
\section{Algoritme}\label{Code:Algorithm}
\begin{lstlisting}[caption={Algorithm}]
class AlgorithmPath: public Algorithm{
public:
	AlgorithmPath( Graph *g ): Algorithm( g ){
		containerAdd();
		m_container = &container(0);
		m_container->push_back( (new ContainerElement())->setNode(graph()->node(1)) );
	}
	
	void run(){
		//For each node in our container that we considered reachable
		for( int i = 0; i < m_container->size(); i++ ){
			//Store this node temporarily
			const Node currentNode = *(*m_container)[i]->node();
			//For each edge in the graph
			for( int j = 0; j < graph()->numEdges(); j++ ){
				//Store this edge temporarily
				const Edge currentEdge = graph()->edge(j);
				
				//If this edge starts from this node
				if( currentEdge.from() == currentNode ){
					highlight(currentEdge);
					bool alreadyContained = false;
					for( int k = 0; k < m_container->size() && !alreadyContained; k++ )
						alreadyContained = currentEdge.to() == *(*m_container)[k]->node();
					if(!alreadyContained)
						m_container->push_back( (new ContainerElement)->setNode(currentEdge.to()) );
				}
			}
		}
		printf("Reachable nodes:\n");
		for( int i = 0; i < m_container->size(); i++ ){
			printf( "\td\n", (*m_container)[i]->node()->identifier() );
		}
	}
private:
	Container *m_container;
};

\end{lstlisting}
\clearpage
\section{Visualizer}\label{Code:Visualizer}

\begin{lstlisting}[caption={Visualizer}]
#include<stdio.h> 
#include<QApplication>
#include<Graph.h>
#include<Algorithm.h>
#include<Visualizer.h>
#include<ContainerElement.h>
#include"AlgKruskal.h"

int main( int argc, char *argv[] ){
	QApplication app(argc, argv);
	
	Graph *graph = Graph::fromFile( "tree.graph" );
	Algorithm *a = new AlgKruskal( graph );
	Visualizer *visualizer = new Visualizer;
	visualizer->addAlgorithm(a);
	visualizer->show();
	a->run();
	
	return app.exec();
}
\end{lstlisting}
\clearpage
\section{Plugin}\label{Code:Plugin}

\begin{lstlisting}[caption={AlgWarshallPlugin.h}]
#ifndef ALGWARSHALLPLUGIN_H
#define ALGWARSHALLPLUGIN_H

#include<AlgorithmInterface.h>
#include<Algorithm.h>
#include"AlgWarshall.h"
#include<QObject>

class AlgWarshallPlugin: public QObject, AlgorithmInterface{
Q_OBJECT
Q_INTERFACES(AlgorithmInterface)
public:
	virtual Algorithm *createAlgorithm( Graph *g );
	virtual QString name()const{ return "Warshall's Algoritme"; }
	virtual bool canAcceptGraph( Graph *g );
private:

};

#endif
\end{lstlisting}

\begin{lstlisting}[caption={AlgWarshallPlugin.cpp}]
#include"AlgWarshallPlugin.h" 
#include<stdio.h>

Algorithm *AlgWarshallPlugin::createAlgorithm( Graph *g ){
	return new AlgWarshall(g);
}

bool AlgWarshallPlugin::canAcceptGraph( Graph *g ){
	return true;
}

#include<QtGui>
Q_EXPORT_PLUGIN2(algwarshallplugin, AlgWarshallPlugin)
\end{lstlisting}

\begin{thebibliography}{9}
\bibitem{cursus}
	Prof. dr. Marc Gyssens,
	\emph{Algoritmen en datastructuren in ICT}.
	Universiteit Hasselt,
	2008-2009.
\bibitem{complexiteit}
	Michael Sipser,
	\emph{Introduction to the Theory of Computation}.
	Thomson Course Technology,
	Second Edition,
	International Edition,
	2006.
\bibitem{qt:download}
	qt.nokia.com/downloads/ (\today)
\bibitem{graphviz:download}
	www.graphviz.org/Download.php (\today)
\bibitem{graphviz:dot}
	www.graphviz.org/content/dot-language (\today)
\end{thebibliography}

\end{document}








